Count of pairs in an Array whose sum is Prime | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool * sieveOfEratosthenes ( int N ) { bool * isPrime = new bool [ 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 ; } int numPairsWithPrimeSum ( int * arr , int n ) { int N = 2 * 1000000 ; bool * 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 ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << numPairsWithPrimeSum ( arr , n ) ; return 0 ; }