Count twin prime pairs in an Array

0 0 6 minutes read

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 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>

Output:

Time Complexity: O(sqrt(M)*N²), 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 zambiatek!