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
function sieveOfEratosthenes ( N ) { let isPrime = Array . from ( { length : N + 1 } , ( _ , i ) => 0 ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { isPrime [ i ] = true ; } isPrime [ 0 ] = false ; isPrime [ 1 ] = false ; for ( let i = 2 ; i * i <= N ; i ++ ) { if ( isPrime [ i ] == true ) { let j = 2 ; while ( i * j <= N ) { isPrime [ i * j ] = false ; j ++ ; } } } return isPrime ; } function numPairsWithPrimeSum ( arr , n ) { let N = 2 * 1000000 ; let isPrime = sieveOfEratosthenes ( N ) ; let count = 0 ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { let sum = arr [ i ] + arr [ j ] ; if ( isPrime [ sum ] ) { count ++ ; } } } return count ; } let arr = [ 1 , 2 , 3 , 4 , 5 ] ; let n = arr . length ; document . write ( numPairsWithPrimeSum ( arr , n ) ) ;