Dado un entero positivo N , la tarea es encontrar el número de números primos menores o iguales a N que se pueden representar como una suma de dos números primos .
Ejemplos:
Entrada: N = 6
Salida: 1
Explicación:
5 es el único número primo en el rango [1, 6] que se puede representar como la suma de 2 números primos, es decir, 5 = 2 + 3, donde 2, 3 y 5 son todos primos
Por lo tanto, la cuenta es 2.Entrada: N = 14
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es considerar todos los pares posibles (i, j) en el rango [1, N] y si i y j son números primos y (i + j) se encuentra en el rango [1 , N] luego incrementa el conteo de números primos. Después de verificar todos los pares posibles, imprima el valor del conteo total obtenido.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la siguiente observación:
- A excepción del 2 , todos los números primos son impares .
- No es posible representar un número primo (que es impar ) como una suma de dos números primos impares, por lo que uno de los dos números primos debe ser 2 .
- Entonces, para que un número primo X sea una suma de dos números primos, X – 2 también debe ser primo.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array, diga primo[] de tamaño 10 5 , y complete todos los números primos hasta 10 5 usando el Tamiz de Eratóstenes .
- Inicialice una array auxiliar dp[] del tamaño (N + 1) donde dp[i] es el recuento de números primos menores o iguales que i que se pueden representar como una suma de 2 números primos .
- Iterar sobre el rango [2, N] usando la variable i y realizar los siguientes pasos:
- Actualice el valor de dp[i – 1] como la suma de dp[i – 1] y dp[i] .
- Compruebe si prime[i] y prime[i – 2] son verdaderos , luego incremente el valor de dp[i] en 1 .
- Después de completar los pasos anteriores, imprima el valor de dp[N] como el conteo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
void SieveOfEratosthenes(
int n, bool prime[])
{
// Set 0 and 1 as non-prime
prime[0] = 0;
prime[1] = 0;
for (int p = 2; p * p <= n; p++) {
// If p is prime
if (prime[p] == true) {
// Set all multiples
// of p as non-prime
for (int i = p * p;
i <= n; i += p) {
prime[i] = false;
}
}
}
}
// Function to count prime numbers
// up to N that can be represented
// as the sum of two prime numbers
void countPrime(int n)
{
// Stores all the prime numbers
bool prime[n + 1];
memset(prime, true, sizeof(prime));
// Update the prime array
SieveOfEratosthenes(n, prime);
// Create a dp array of size n + 1
int dp[n + 1];
memset(dp, 0, sizeof(dp));
// Update dp[1] = 0
dp[1] = 0;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
// Add the previous count value
dp[i] += dp[i - 1];
// Increment dp[i] by 1 if i
// and (i - 2) are both prime
if (prime[i] == 1
&& prime[i - 2] == 1) {
dp[i]++;
}
}
// Print the result
cout << dp[n];
}
// Driver Code
int main()
{
int N = 6;
countPrime(N);
return 0;
}
Java
// Java approach for the above approach
class GFG{
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
static void SieveOfEratosthenes(int n, boolean prime[])
{
// Set 0 and 1 as non-prime
prime[0] = false;
prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If p is prime
if (prime[p] == true)
{
// Set all multiples
// of p as non-prime
for(int i = p * p; i <= n; i += p)
{
prime[i] = false;
}
}
}
}
// Function to count prime numbers
// up to N that can be represented
// as the sum of two prime numbers
static void countPrime(int n)
{
// Stores all the prime numbers
boolean prime[] = new boolean[n + 1];
for(int i = 0; i < prime.length; i++)
{
prime[i] = true;
}
// Update the prime array
SieveOfEratosthenes(n, prime);
// Create a dp array of size n + 1
int dp[] = new int[n + 1];
for(int i = 0; i < dp.length; i++)
{
dp[i] = 0;
}
// Update dp[1] = 0
dp[1] = 0;
// Iterate over the range [2, N]
for(int i = 2; i <= n; i++)
{
// Add the previous count value
dp[i] += dp[i - 1];
// Increment dp[i] by 1 if i
// and (i - 2) are both prime
if (prime[i] == true &&
prime[i - 2] == true)
{
dp[i]++;
}
}
// Print the result
System.out.print(dp[n]);
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
countPrime(N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to store all prime numbers # up to N using Sieve of Eratosthenes def SieveOfEratosthenes(n, prime): # Set 0 and 1 as non-prime prime[0] = 0 prime[1] = 0 p = 2 while p * p <= n: # If p is prime if (prime[p] == True): # Set all multiples # of p as non-prime for i in range(p * p, n + 1, p): prime[i] = False p += 1 # Function to count prime numbers # up to N that can be represented # as the sum of two prime numbers def countPrime(n): # Stores all the prime numbers prime = [True] * (n + 1) # Update the prime array SieveOfEratosthenes(n, prime) # Create a dp array of size n + 1 dp = [0] * (n + 1) # Update dp[1] = 0 dp[1] = 0 # Iterate over the range [2, N] for i in range(2, n + 1): # Add the previous count value dp[i] += dp[i - 1] # Increment dp[i] by 1 if i # and (i - 2) are both prime if (prime[i] == 1 and prime[i - 2] == 1): dp[i] += 1 # Print the result print(dp[n]) # Driver Code if __name__ == "__main__": N = 6 countPrime(N) # This code is contributed by mohit ukasp
C#
// C# program for the above approach
using System;
class GFG{
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
static void SieveOfEratosthenes(int n, bool[] prime)
{
// Set 0 and 1 as non-prime
prime[0] = false;
prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If p is prime
if (prime[p] == true)
{
// Set all multiples
// of p as non-prime
for(int i = p * p; i <= n; i += p)
{
prime[i] = false;
}
}
}
}
// Function to count prime numbers
// up to N that can be represented
// as the sum of two prime numbers
static void countPrime(int n)
{
// Stores all the prime numbers
bool[] prime = new bool[n + 1];
for(int i = 0; i < prime.Length; i++)
{
prime[i] = true;
}
// Update the prime array
SieveOfEratosthenes(n, prime);
// Create a dp array of size n + 1
int[] dp = new int[n + 1];
for(int i = 0; i < dp.Length; i++)
{
dp[i] = 0;
}
// Update dp[1] = 0
dp[1] = 0;
// Iterate over the range [2, N]
for(int i = 2; i <= n; i++)
{
// Add the previous count value
dp[i] += dp[i - 1];
// Increment dp[i] by 1 if i
// and (i - 2) are both prime
if (prime[i] == true &&
prime[i - 2] == true)
{
dp[i]++;
}
}
// Print the result
Console.Write(dp[n]);
}
// Driver code
static void Main()
{
int N = 6;
countPrime(N);
}
}
// This code is contributed by abhinavjain194
Javascript
<script>
// Javascript program for the above approach
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
function SieveOfEratosthenes(n, prime)
{
// Set 0 and 1 as non-prime
prime[0] = 0;
prime[1] = 0;
for(var p = 2; p * p <= n; p++)
{
// If p is prime
if (prime[p] == Boolean(true))
{
// Set all multiples
// of p as non-prime
for(var i = p * p;i <= n; i += p)
{
prime[i] = Boolean(false);
}
}
}
}
// Function to count prime numbers
// up to N that can be represented
// as the sum of two prime numbers
function countPrime(n)
{
// Stores all the prime numbers
var prime = new Array(n + 1);
var x = new Boolean(true);
prime.fill(x);
// Update the prime array
SieveOfEratosthenes(n, prime);
// Create a dp array of size n + 1
var dp = new Array(n + 1);
dp.fill(0);
// Update dp[1] = 0
dp[1] = 0;
// Iterate over the range [2, N]
for(var i = 2; i <= n; i++)
{
// Add the previous count value
dp[i] += dp[i - 1];
// Increment dp[i] by 1 if i
// and (i - 2) are both prime
if (prime[i] == Boolean(true) &&
prime[i - 2] == Boolean(true))
{
dp[i]++;
}
}
// Print the result
document.write(dp[n]);
}
// Driver code
var n = 6;
countPrime(n);
// This code is contributed by SoumikMondal
</script>
Producción:
1
Complejidad de tiempo: O(N * log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nihalkumar703 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA