Count of pairs in an Array whose sum is Prime | Java code to find number of pairs of elements 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
import java . io . * ; import java . util . * ; class GFG { public static boolean [ ] sieveOfEratosthenes ( int N ) { boolean [ ] isPrime = new boolean [ N + 1 ] ; for ( int i = 0 ; i < N + 1 ; i ++ ) { isPrime [ i ] = true ; } isPrime [ 0 ] = false ; isPrime [ 1 ] = false ; for ( int i = 2 ; i * i <= N ; i ++ ) { if ( isPrime [ i ] == true ) { int j = 2 ; while ( i * j <= N ) { isPrime [ i * j ] = false ; j ++ ; } } } return isPrime ; } public static int numPairsWithPrimeSum ( int [ ] arr , int n ) { int N = 2 * 1000000 ; boolean [ ] isPrime = sieveOfEratosthenes ( N ) ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int sum = arr [ i ] + arr [ j ] ; if ( isPrime [ sum ] ) { count ++ ; } } } return count ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 , 4 , 5 } ; int n = arr . length ; System . out . println ( numPairsWithPrimeSum ( arr , n ) ) ; } }