human
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"
How can the above be solved in Python?
assistant
#Here is code to count of pairs in an Array whose sum is Prime and the other steps required.
 def sieveOfEratosthenes ( N ) :
	isPrime = [ True for i in range ( N + 1 ) ]
	isPrime [ 0 ] = False
	isPrime [ 1 ] = False
	i = 2
	while ( ( i * i ) <= N ) :
		if ( isPrime [ i ] ) :
			j = 2
			while ( i * j <= N ) :
				isPrime [ i * j ] = False
				j += 1
		i += 1
	return isPrime
def numPairsWithPrimeSum ( arr , n ) :
	N = 2 * 1000000
	isPrime = sieveOfEratosthenes ( N )
	count = 0
	for i in range ( n ) :
		for j in range ( i + 1 , n ) :
			sum = arr [ i ] + arr [ j ]
			if ( isPrime [ sum ] ) :
				count += 1
	return count
if __name__ == " _ _ main _ _ " :
	arr = [ 1 , 2 , 3 , 4 , 5 ]
	n = len ( arr )
	print ( numPairsWithPrimeSum ( arr , n ) )