Dada una array arr[] de N números naturales. La tarea es contar todos los pares posibles en el arr[] que son Twin Primes .
Los primos gemelos son aquellos números que son primos y tienen una diferencia de dos (2) entre los dos números primos. En otras palabras, un primo gemelo es un primo que tiene un espacio primo de dos.
Ejemplos:
Entrada: arr[] = { 2, 3, 5, 7}
Salida: 2
Explicación:
Los 2 pares son (3, 5) y (5, 7).Entrada: arr[] = { 2, 4, 6, 11}
Salida: 0
Explicación:
No existen tales pares que formen Twin Primes.
Enfoque ingenuo:
la idea es encontrar todos los pares posibles en la array dada arr[] y verificar si ambos elementos en pares son números primos y difieren en 2 , luego los pares actuales forman Twin Primes .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count Twin
// Prime pairs in array
#include <bits/stdc++.h>
using namespace std;
// A utility function to check if
// the number n is prime or not
bool isPrime(int n)
{
// Base Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// Check to skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6) {
// If n is divisible by i and i+2
// then it is not prime
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// A utility function that check
// if n1 and n2 are Twin Primes
// or not
bool twinPrime(int n1, int n2)
{
return (isPrime(n1)
&& isPrime(n2)
&& abs(n1 - n2) == 2);
}
// Function to find Twin Prime
// pairs from the given array
int countTwinPairs(int arr[], int n)
{
int count = 0;
// Iterate through all pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Increment count if
// twin prime pair
if (twinPrime(arr[i], arr[j])) {
count++;
}
}
}
return count;
}
// Driver's code
int main()
{
int arr[] = { 2, 3, 5, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call to find
// Twin Primes pair
cout << countTwinPairs(arr, n);
return 0;
}
Java
// Java program to count Twin
// Prime pairs in array
import java.util.*;
class GFG{
// A utility function to check if
// the number n is prime or not
static boolean isPrime(int n)
{
// Base Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// Check to skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6) {
// If n is divisible by i and i+2
// then it is not prime
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// A utility function that check
// if n1 and n2 are Twin Primes
// or not
static boolean twinPrime(int n1, int n2)
{
return (isPrime(n1)
&& isPrime(n2)
&& Math.abs(n1 - n2) == 2);
}
// Function to find Twin Prime
// pairs from the given array
static int countTwinPairs(int arr[], int n)
{
int count = 0;
// Iterate through all pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Increment count if
// twin prime pair
if (twinPrime(arr[i], arr[j])) {
count++;
}
}
}
return count;
}
// Driver's code
public static void main(String[] args)
{
int arr[] = { 2, 3, 5, 11 };
int n = arr.length;
// Function call to find
// Twin Primes pair
System.out.print(countTwinPairs(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python 3
# Python 3 program to count Twin # Prime pairs in array from math import sqrt # A utility function to check if # the number n is prime or not def isPrime(n): # Base Cases if (n <= 1): return False if (n <= 3): return True # Check to skip middle five # numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False for i in range(5,int(sqrt(n))+1,6): # If n is divisible by i and i+2 # then it is not prime if (n % i == 0 or n % (i + 2) == 0): return False return True # A utility function that check # if n1 and n2 are Twin Primes # or not def twinPrime(n1, n2): return (isPrime(n1) and isPrime(n2) and abs(n1 - n2) == 2) # Function to find Twin Prime # pairs from the given array def countTwinPairs(arr, n): count = 0 # Iterate through all pairs for i in range(n): for j in range(i + 1,n): # Increment count if # twin prime pair if (twinPrime(arr[i], arr[j])): count += 1 return count # Driver's code if __name__ == '__main__': arr = [2, 3, 5, 11] n = len(arr) # Function call to find # Twin Primes pair print(countTwinPairs(arr, n)) # This code is contributed by Surendra_Gangwar
C#
// C# program to count Twin
// Prime pairs in array
using System;
class GFG{
// A utility function to check if
// the number n is prime or not
static bool isPrime(int n)
{
// Base Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// Check to skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6) {
// If n is divisible by i and i+2
// then it is not prime
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// A utility function that check
// if n1 and n2 are Twin Primes
// or not
static bool twinPrime(int n1, int n2)
{
return (isPrime(n1)
&& isPrime(n2)
&& Math.Abs(n1 - n2) == 2);
}
// Function to find Twin Prime
// pairs from the given array
static int countTwinPairs(int []arr, int n)
{
int count = 0;
// Iterate through all pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Increment count if
// twin prime pair
if (twinPrime(arr[i], arr[j])) {
count++;
}
}
}
return count;
}
// Driver's code
public static void Main(String[] args)
{
int []arr = { 2, 3, 5, 11 };
int n = arr.Length;
// Function call to find
// Twin Primes pair
Console.Write(countTwinPairs(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the
// above approach
// A utility function to check if
// the number n is prime or not
function isPrime(n)
{
// Base Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// Check to skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (var i = 5; i * i <= n; i += 6) {
// If n is divisible by i and i+2
// then it is not prime
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// A utility function that check
// if n1 and n2 are Twin Primes
// or not
function twinPrime(n1, n2)
{
return (isPrime(n1)
&& isPrime(n2)
&& Math.abs(n1 - n2) == 2);
}
// Function to find Twin Prime
// pairs from the given array
function countTwinPairs(arr, n)
{
var count = 0;
// Iterate through all pairs
for (var i = 0; i < n; i++) {
for (var j = i + 1; j < n; j++) {
// Increment count if
// twin prime pair
if (twinPrime(arr[i], arr[j])) {
count++;
}
}
}
return count;
}
// Driver code
var arr=[ 2, 3, 5, 11 ];
var n = arr.length;
document.write(countTwinPairs(arr, n));
// This code is contributed by Shivanisingh
</script>
Producción:
1
Complejidad de tiempo: O(sqrt(M)*N 2 ), donde N es el número de elementos en la array dada y M es el elemento máximo en la array.
Enfoque eficiente:
- Precalcule todos los números primos hasta el número máximo en la array dada arr[] usando Sieve of Eratosthenes .
- Almacene todas las frecuencias de todos los elementos para la array dada arr[] .
- Ordena la array dada arr[] .
- Para cada elemento de la array , compruebe si el elemento es primo o no.
- Si el elemento es un número primo , compruebe si (elemento+2) es un número primo y está presente en la array dada arr[] .
- Si el (elemento+2) está presente, entonces la frecuencia de (elemento+2) dará el conteo de pares para el elemento actual.
- Repita el paso anterior para todos los elementos de la array .