Given an array arr[] of N natural numbers. The task is to count all possible pairs in the arr[] that are Twin Primes.
A Twin prime are those numbers that are prime and have a difference of two ( 2 ) between the two prime numbers. In other words, a twin prime is a prime that has a prime gap of two.
Examples:
Input: arr[] = { 2, 3, 5, 7}
Output: 2
Explanation:
The 2 pairs are (3, 5) and (5, 7).Input: arr[] = { 2, 4, 6, 11}
Output: 0
Explanation:
There are no such pairs forming Twin Primes.
Naive Approach:
The idea is to find all possible pairs in the given array arr[] and check whether both the elements in pairs are Prime Numbers and they differ by 2, then the current pairs form Twin Primes.
Below is the implementation of the above approach:
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 notbool 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 notbool twinPrime(int n1, int n2){ return (isPrime(n1) && isPrime(n2) && abs(n1 - n2) == 2);}// Function to find Twin Prime// pairs from the given arrayint 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 codeint 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 arrayimport java.util.*;class GFG{ // A utility function to check if// the number n is prime or notstatic 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 notstatic 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 arraystatic 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 codepublic 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 arrayfrom math import sqrt# A utility function to check if# the number n is prime or notdef 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 notdef twinPrime(n1, n2): return (isPrime(n1) and isPrime(n2) and abs(n1 - n2) == 2)# Function to find Twin Prime# pairs from the given arraydef 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 codeif __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 arrayusing System;class GFG{ // A utility function to check if// the number n is prime or notstatic 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 notstatic 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 arraystatic 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 codepublic 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 notfunction 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 notfunction twinPrime(n1, n2){ return (isPrime(n1) && isPrime(n2) && Math.abs(n1 - n2) == 2);} // Function to find Twin Prime// pairs from the given arrayfunction 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 codevar arr=[ 2, 3, 5, 11 ];var n = arr.length;document.write(countTwinPairs(arr, n));// This code is contributed by Shivanisingh</script> |
Output:
1
Time Complexity: O(sqrt(M)*N2), where N is the number of elements in the given array and M is the maximum element in the array
Auxiliary Space: O(1)
Efficient Approach:
- Precompute all the Prime Numbers till maximum number in the given array arr[] using Sieve of Eratosthenes.
- Store all the frequencies of all elements for the given array arr[].
- Sort the given array arr[].
- For each element in the array, check if the element is prime or not.
- If the element is, prime number then check if (element+2) is a prime number and is present in the given array arr[].
- If the (element+2) is present, then the frequency of (element+2) will give the count of pairs for the current element.
- Repeat the above step for all the elements in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
