Count Sexy Prime Pairs in the given array | 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 ) s ; 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 ) s pair
def computePrime ( N ) : NEW_LINE INDENT Prime = [ True ] * ( N + 1 ) NEW_LINE Prime [ 0 ] = False NEW_LINE Prime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while i * i <= N : NEW_LINE INDENT if ( Prime [ i ] ) : NEW_LINE INDENT for j in range ( i * i , N , i ) : NEW_LINE INDENT Prime [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT return Prime NEW_LINE DEDENT def countSexyPairs ( arr , n ) : NEW_LINE INDENT maxE = max ( arr ) NEW_LINE Prime = computePrime ( maxE ) NEW_LINE count = 0 NEW_LINE freq = [ 0 ] * ( maxE + 6 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT arr . sort ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( Prime [ arr [ i ] ] ) : NEW_LINE INDENT if ( ( arr [ i ] + 6 ) <= ( maxE ) and freq [ arr [ i ] + 6 ] > 0 and Prime [ arr [ i ] + 6 ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 6 , 7 , 5 , 11 , 13 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countSexyPairs ( arr , n ) ) NEW_LINE DEDENT