Count Sexy Prime Pairs in the given array

Software Development
#1

Hello Everyone,

Given an array arr[] of size N containing natural numbers, the task is to count all possible pairs in the arr[] that are Sexy Prime Pairs.

A SPP (Sexy Prime Pair) are those numbers that are prime and having a difference 6 between the prime numbers. In other words, an SPP (Sexy Prime Pair) is a prime that has a prime gap of six.

Examples:

Input: arr[] = { 6, 7, 5, 11, 13 }
Output: 2
Explanation:
The 2 pairs are (5, 11) and (7, 13).
Input: arr[] = { 2, 4, 6, 11 }
Output: 0
Explanation:
There are no such pairs forming SPP (Sexy Prime Pair).

Efficient Approach:
The method mentioned above can be optimized by the following steps:

  1. Precompute all the Prime Numbers till maximum number in the given array arr[] using Sieve of Eratosthenes.
  2. Store all the frequency of all element for the given array and sort the array.
  3. For each element in the array, check if the element is prime or not.
  4. If the element is prime, then check if (element + 6) is a prime number or not and is present in the given array.
  5. If the (element + 6) is present, then the frequency of (element + 6) will give the count of pairs for the current element.
  6. Repeat the above step for all the element in the array.

Below is the implementation of the above approach:

// C++ program to count Sexy

// Prime pairs in array

#include <bits/stdc++.h>

using namespace std;

// To store check the prime

// number

vector< bool > Prime;

// A utility function that find

// the Prime Numbers till N

void computePrime( int N)

{

// Resize the Prime Number

Prime.resize(N + 1, true );

Prime[0] = Prime[1] = false ;

// Loop till sqrt(N) to find

// prime numbers and make their

// multiple false in the bool

// array Prime

for ( int i = 2; i * i <= N; i++) {

if (Prime[i]) {

for ( int j = i * i; j < N; j += i) {

Prime[j] = false ;

}

}

}

}

// Function that returns the count

// of SPP (Sexy Prime Pair) Pairs

int countSexyPairs( int arr[], int n)

{

// Find the maximum element in

// the given array arr[]

int maxE = *max_element(arr, arr + n);

// Function to calculate the

// prime numbers till N

computePrime(maxE);

// To store the count of pairs

int count = 0;

// To store the frequency of

// element in the array arr[]

int freq[maxE + 1] = { 0 };

for ( int i = 0; i < n; i++) {

freq[arr[i]]++;

}

// Sort before traversing the array

sort(arr, arr + n);

// Traverse the array and find

// the pairs with SPP (Sexy Prime Pair)

for ( int i = 0; i < n; i++) {

// If current element is

// Prime, then check for

// (current element + 6)

if (Prime[arr[i]]) {

if (freq[arr[i] + 6] > 0

&& Prime[arr[i] + 6]) {

count++;

}

}

}

// Return the count of pairs

return count;

}

// Driver code

int main()

{

int arr[] = { 6, 7, 5, 11, 13 };

int n = sizeof (arr) / sizeof (arr[0]);

// Function call to find

// SPP (Sexy Prime Pair) pair

cout << countSexyPairs(arr, n);

return 0;

}

Output:

2

Time Complexity: O(N * sqrt(M)), where N is the number of elements in the given array, and M is the maximum element in the array.
Auxiliary Space Complexity: O(N)