Count Sexy Prime Pairs in the given array | C ++ program to count Sexy Prime pairs in array ; To store check the prime number ; A utility function that find the Prime Numbers till N ; Resize the Prime Number ; Loop till sqrt ( N ) to find prime numbers and make their multiple false in the bool array Prime ; Function that returns the count of SPP ( Sexy Prime Pair ) Pairs ; Find the maximum element in the given array arr [ ] ; Function to calculate the prime numbers till N ; To store the count of pairs ; To store the frequency of element in the array arr [ ] ; Sort before traversing the array ; Traverse the array and find the pairs with SPP ( Sexy Prime Pair ) ; If current element is Prime , then check for ( current element + 6 ) ; Return the count of pairs ; Driver code ; Function call to find SPP ( Sexy Prime Pair ) pair
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < bool > Prime ; void computePrime ( int N ) { Prime . resize ( N + 1 , true ) ; Prime [ 0 ] = Prime [ 1 ] = false ; for ( int i = 2 ; i * i <= N ; i ++ ) { if ( Prime [ i ] ) { for ( int j = i * i ; j < N ; j += i ) { Prime [ j ] = false ; } } } } int countSexyPairs ( int arr [ ] , int n ) { int maxE = * max_element ( arr , arr + n ) ; computePrime ( maxE ) ; int count = 0 ; int freq [ maxE + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } sort ( arr , arr + n ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( Prime [ arr [ i ] ] ) { if ( freq [ arr [ i ] + 6 ] > 0 && Prime [ arr [ i ] + 6 ] ) { count ++ ; } } } return count ; } int main ( ) { int arr [ ] = { 6 , 7 , 5 , 11 , 13 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countSexyPairs ( arr , n ) ; return 0 ; }