# Count Sexy Prime Pairs in the given array

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)