Recuento de primos en un rango dado que se puede expresar como suma de cuadrados perfectos

Dados dos números enteros L y R , la tarea es encontrar el número de números primos en el rango [L, R] que se pueden representar por la suma de dos cuadrados de dos números.
Ejemplos:

Entrada: L = 1, R = 5
Salida: 1
Explicación:
El único número primo que se puede expresar como la suma de dos cuadrados perfectos en el rango dado es 5 (2 ² + 1 ² )
Entrada: L = 7, R = 42
Salida : 5
Explicación:
Los números primos en el rango dado que se pueden expresar como la suma de dos cuadrados perfectos son:
13 = 2 ² + 3 ²
17 = 1 ² + 4 ²
29 = 5 ² + 2 ²
37 = 1 ² + 6 ²
41 = 5 ² + 4 ²

Enfoque:
El problema dado se puede resolver utilizando el pequeño teorema de Fermat , que establece que un número primo p se puede expresar como la suma de dos cuadrados si p satisface la siguiente ecuación:

(p – 1) % 4 == 0

Siga los pasos a continuación para resolver el problema:

Atraviesa el rango [L, R] .
Para cada número, compruebe si es un número primo o no .
Si es así, compruebe si el número primo es de la forma 4K + 1 . Si es sp, aumente la cuenta .
Después de atravesar el rango completo, imprima el conteo .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a prime number
// satisfies the condition to be
// expressed as sum of two perfect squares
bool sumSquare(int p)
{
    return (p - 1) % 4 == 0;
}
 
// Function to check if a
// number is prime or not
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return true;
 
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to return the count of primes
// in the range which can be expressed as
// the sum of two squares
int countOfPrimes(int L, int R)
{
    int count = 0;
    for (int i = L; i <= R; i++) {
 
        // If i is a prime
        if (isPrime(i)) {
 
            // If i can be expressed
            // as the sum of two squares
            if (sumSquare(i))
                count++;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int L = 5, R = 41;
    cout << countOfPrimes(L, R);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to check if a prime number
// satisfies the condition to be
// expressed as sum of two perfect
// squares
static boolean sumSquare(int p)
{
    return (p - 1) % 4 == 0;
}
 
// Function to check if a
// number is prime or not
static boolean isPrime(int n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return true;
 
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to return the count of primes
// in the range which can be expressed as
// the sum of two squares
static int countOfPrimes(int L, int R)
{
    int count = 0;
    for(int i = L; i <= R; i++)
    {
 
        // If i is a prime
        if (isPrime(i))
        {
 
            // If i can be expressed
            // as the sum of two squares
            if (sumSquare(i))
                count++;
        }
    }
     
    // Return the count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int L = 5, R = 41;
 
    System.out.println(countOfPrimes(L, R));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the
# above approach
 
# Function to check if a prime number
# satisfies the condition to be
# expressed as sum of two perfect
# squares
def sumsquare(p):
   
  return (p - 1) % 4 == 0
 
# Function to check if a
# number is prime or not
def isprime(n):
   
  # Corner cases
  if n <= 1:
    return False
  if n <= 3:
    return True
  if (n % 2 == 0) or (n % 3 == 0):
    return False
   
  i = 5
  while (i * i <= n):
    if ((n % i == 0) or
        (n % (i + 2) == 0)):
      return False
    i += 6
     
  return True
 
# Function to return the count of primes
# in the range which can be expressed as
# the sum of two squares
def countOfPrimes(L, R):
   
  count = 0
  for i in range(L, R + 1):
     
    # If i is a prime
    if (isprime(i)):
       
      # If i can be expressed
      # as the sum of two squares
      if sumsquare(i):
        count += 1
 
  # Return the count
  return count
 
# Driver code
if __name__=='__main__':
   
  L = 5
  R = 41
  print(countOfPrimes(L, R))
     
# This code is contributed by virusbuddah_

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to check if a prime number
// satisfies the condition to be
// expressed as sum of two perfect
// squares
static bool sumSquare(int p)
{
    return (p - 1) % 4 == 0;
}
 
// Function to check if a
// number is prime or not
static bool isPrime(int n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return true;
 
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to return the count of primes
// in the range which can be expressed as
// the sum of two squares
static int countOfPrimes(int L, int R)
{
    int count = 0;
    for(int i = L; i <= R; i++)
    {
 
        // If i is a prime
        if (isPrime(i))
        {
 
            // If i can be expressed
            // as the sum of two squares
            if (sumSquare(i))
                count++;
        }
    }
     
    // Return the count
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    int L = 5, R = 41;
 
    Console.WriteLine(countOfPrimes(L, R));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program to implement
// the above approach
 
    // Function to check if a prime number
    // satisfies the condition to be
    // expressed as sum of two perfect
    // squares
    function sumSquare(p) {
        return (p - 1) % 4 == 0;
    }
 
    // Function to check if a
    // number is prime or not
    function isPrime(n) {
 
        // Corner cases
        if (n <= 1)
            return false;
 
        if (n <= 3)
            return true;
 
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to return the count of primes
    // in the range which can be expressed as
    // the sum of two squares
    function countOfPrimes(L , R) {
        var count = 0;
        for (var i = L; i <= R; i++) {
 
            // If i is a prime
            if (isPrime(i)) {
 
                // If i can be expressed
                // as the sum of two squares
                if (sumSquare(i))
                    count++;
            }
        }
 
        // Return the count
        return count;
    }
 
    // Driver code
        var L = 5, R = 41;
        document.write(countOfPrimes(L, R));
 
// This code is contributed by todaysgaurav
</script>

Producción:

Complejidad de Tiempo: O(N ^3/2 )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta