Dado un número entero N , la tarea es contar el número de pares de números primos en el rango [1, N] de modo que la diferencia entre los elementos de cada par también sea un número primo .
Ejemplos:
Entrada: N = 5
Salida: 2
Explicaciones:
Par de números primos en el rango [1, 5] cuya diferencia entre elementos también es un número primo son:
(2, 5) = 3 (Número primo)
(3, 5) = 2 (Número primo)
Por lo tanto, la cuenta de pares de números primos cuya diferencia también es un número primo es 2.Entrada: N = 11
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los pares posibles de elementos en el rango [1, N] y, para cada par, verificar si tanto los elementos como la diferencia entre ambos elementos del par son primos . número o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo.
Complejidad de Tiempo: O(N 2 * √N)
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
Número impar – Número par = Número impar Número
impar – Número impar = Número par El número
2 es el único número primo par.
Por tanto, el problema se reduce a comprobar sólo aquellos pares de números primos cuya diferencia entre los elementos del par sea igual a 2.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntPairs para almacenar el recuento de pares de números primos de modo que la diferencia entre los elementos de cada par también sea un número primo .
- Inicialice una array, diga sieve[] para verificar si un número en el rango [1, N] es un número primo o no.
- Encuentre todos los números primos en el rango [1, N] usando la criba de Eratóstenes .
- Itere sobre el rango [2, N] , y para cada elemento en el rango dado, verifique si sieve[i] y sieve[i – 2] son verdaderos o no. Si se determina que es cierto, incremente el valor de cntPairs en 2 .
- Finalmente, imprima el valor de cntPairs .
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 find all prime
// numbers in the range [1, N]
vector<bool> SieveOfEratosthenes(
int N)
{
// isPrime[i]: Stores if i is
// a prime number or not
vector<bool> isPrime(N, true);
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for (int p = 2; p * p <= N; p++) {
// If P is a prime number
if (isPrime[p]) {
// Set all multiple of P
// as non-prime
for (int i = p * p; i <= N;
i += p) {
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to count pairs of
// prime numbers in the range [1, N]
// whose difference is prime
int cntPairsdiffOfPrimeisPrime(int N)
{
// Function to count pairs of
// prime numbers whose difference
// is also a prime number
int cntPairs = 0;
// isPrime[i]: Stores if i is
// a prime number or not
vector<bool> isPrime
= SieveOfEratosthenes(N);
// Iterate over the range [2, N]
for (int i = 2; i <= N; i++) {
// If i and i - 2 is
// a prime number
if (isPrime[i] &&
isPrime[i - 2]) {
// Update cntPairs
cntPairs += 2;
}
}
return cntPairs;
}
// Driver Code
int main()
{
int N = 5;
cout << cntPairsdiffOfPrimeisPrime(N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find all prime
// numbers in the range [1, N]
public static boolean[] SieveOfEratosthenes(int N)
{
// isPrime[i]: Stores if i is
// a prime number or not
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for(int p = 2; p * p <= N; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for(int i = p * p; i <= N; i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to count pairs of
// prime numbers in the range [1, N]
// whose difference is prime
public static int cntPairsdiffOfPrimeisPrime(int N)
{
// Function to count pairs of
// prime numbers whose difference
// is also a prime number
int cntPairs = 0;
// isPrime[i]: Stores if i is
// a prime number or not
boolean[] isPrime = SieveOfEratosthenes(N);
// Iterate over the range [2, N]
for(int i = 2; i <= N; i++)
{
// If i and i - 2 is
// a prime number
if (isPrime[i] && isPrime[i - 2])
{
// Update cntPairs
cntPairs += 2;
}
}
return cntPairs;
}
// Driver Code
public static void main(String args[])
{
int N = 5;
System.out.println(cntPairsdiffOfPrimeisPrime(N));
}
}
// This code is contributed by hemanth gadarla
Python3
# Python3 program to implement # the above approach from math import sqrt # Function to find all prime # numbers in the range [1, N] def SieveOfEratosthenes(N): # isPrime[i]: Stores if i is # a prime number or not isPrime = [True for i in range(N + 1)] isPrime[0] = False isPrime[1] = False # Calculate all prime numbers up to # Max using Sieve of Eratosthenes for p in range(2, int(sqrt(N)) + 1, 1): # If P is a prime number if (isPrime[p]): # Set all multiple of P # as non-prime for i in range(p * p, N + 1, p): # Update isPrime isPrime[i] = False return isPrime # Function to count pairs of # prime numbers in the range [1, N] # whose difference is prime def cntPairsdiffOfPrimeisPrime(N): # Function to count pairs of # prime numbers whose difference # is also a prime number cntPairs = 0 # isPrime[i]: Stores if i is # a prime number or not isPrime = SieveOfEratosthenes(N) # Iterate over the range [2, N] for i in range(2, N + 1, 1): # If i and i - 2 is # a prime number if (isPrime[i] and isPrime[i - 2]): # Update cntPairs cntPairs += 2 return cntPairs # Driver Code if __name__ == '__main__': N = 5 print(cntPairsdiffOfPrimeisPrime(N)) # This code is contributed by ipg2016107
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find all prime
// numbers in the range [1, N]
public static bool[] SieveOfEratosthenes(int N)
{
// isPrime[i]: Stores if i is
// a prime number or not
bool[] isPrime = new bool[N + 1];
for(int i = 0; i < N + 1; i++)
{
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for(int p = 2; p * p <= N; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for(int i = p * p; i <= N; i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to count pairs of
// prime numbers in the range [1, N]
// whose difference is prime
public static int cntPairsdiffOfPrimeisPrime(int N)
{
// Function to count pairs of
// prime numbers whose difference
// is also a prime number
int cntPairs = 0;
// isPrime[i]: Stores if i is
// a prime number or not
bool[] isPrime = SieveOfEratosthenes(N);
// Iterate over the range [2, N]
for(int i = 2; i <= N; i++)
{
// If i and i - 2 is
// a prime number
if (isPrime[i] && isPrime[i - 2])
{
// Update cntPairs
cntPairs += 2;
}
}
return cntPairs;
}
// Driver Code
public static void Main()
{
int N = 5;
Console.WriteLine(cntPairsdiffOfPrimeisPrime(N));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find all prime
// numbers in the range [1, N]
function SieveOfEratosthenes(N)
{
// isPrime[i]: Stores if i is
// a prime number or not
let isPrime = [];
for(let i = 0; i < N + 1; i++)
{
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
// Calculate all prime numbers up to
// Max using Sieve of Eratosthenes
for(let p = 2; p * p <= N; p++)
{
// If P is a prime number
if (isPrime[p])
{
// Set all multiple of P
// as non-prime
for(let i = p * p; i <= N; i += p)
{
// Update isPrime
isPrime[i] = false;
}
}
}
return isPrime;
}
// Function to count pairs of
// prime numbers in the range [1, N]
// whose difference is prime
function cntPairsdiffOfPrimeisPrime(N)
{
// Function to count pairs of
// prime numbers whose difference
// is also a prime number
let cntPairs = 0;
// isPrime[i]: Stores if i is
// a prime number or not
let isPrime = SieveOfEratosthenes(N);
// Iterate over the range [2, N]
for(let i = 2; i <= N; i++)
{
// If i and i - 2 is
// a prime number
if (isPrime[i] && isPrime[i - 2])
{
// Update cntPairs
cntPairs += 2;
}
}
return cntPairs;
}
// Driver Code
let N = 5;
document.write(cntPairsdiffOfPrimeisPrime(N));
</script>
Producción:
2
Complejidad de tiempo: O(N * log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sallagondaavinashreddy7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA