Count of pairs in an Array whose sum is Prime | Function for Sieve Of Eratosthenes ; Function to count total number of pairs of elements whose sum is prime ; Driver code
def sieveOfEratosthenes ( N ) : NEW_LINE INDENT isPrime = [ True for i in range ( N + 1 ) ] NEW_LINE isPrime [ 0 ] = False NEW_LINE isPrime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while ( ( i * i ) <= N ) : NEW_LINE INDENT if ( isPrime [ i ] ) : NEW_LINE INDENT j = 2 NEW_LINE while ( i * j <= N ) : NEW_LINE INDENT isPrime [ i * j ] = False NEW_LINE j += 1 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT return isPrime NEW_LINE DEDENT def numPairsWithPrimeSum ( arr , n ) : NEW_LINE INDENT N = 2 * 1000000 NEW_LINE isPrime = sieveOfEratosthenes ( N ) NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT sum = arr [ i ] + arr [ j ] NEW_LINE if ( isPrime [ sum ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( numPairsWithPrimeSum ( arr , n ) ) NEW_LINE DEDENT