Count pairs from a given range whose sum is a Prime Number in that range | C ++ program to implement the above approach ; Function to find all prime numbers in range [ 1 , lmt ] using sieve of Eratosthenes ; segmentedSieve [ i ] : Stores if i is a prime number ( True ) or not ( False ) ; Initialize all elements of segmentedSieve [ ] to false ; Set 0 and 1 as non - prime ; Iterate over the range [ 2 , lmt ] ; If i is a prime number ; Append i into prime ; Set all multiple of i non - prime ; Update Sieve [ j ] ; Function to find all the prime numbers in the range [ low , high ] ; Stores square root of high + 1 ; Stores all the prime numbers in the range [ 1 , lmt ] ; Find all the prime numbers in the range [ 1 , lmt ] ; Stores count of elements in the range [ low , high ] ; segmentedSieve [ i ] : Check if ( i - low ) is a prime number or not ; Traverse the array prime [ ] ; Store smallest multiple of prime [ i ] in the range [ low , high ] ; If lowLim is less than low ; Update lowLim ; Iterate over all multiples of prime [ i ] ; If j not equal to prime [ i ] ; Update segmentedSieve [ j - low ] ; Function to count the number of pairs in the range [ L , R ] whose sum is a prime number in the range [ L , R ] ; segmentedSieve [ i ] : Check if ( i - L ) is a prime number or not ; Stores count of pairs whose sum of elements is a prime and in range [ L , R ] ; Iterate over [ L , R ] ; If ( i - L ) is a prime ; Update cntPairs ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void simpleSieve ( int lmt , vector < int > & prime ) { bool Sieve [ lmt + 1 ] ; memset ( Sieve , true , sizeof ( Sieve ) ) ; Sieve [ 0 ] = Sieve [ 1 ] = false ; for ( int i = 2 ; i <= lmt ; ++ i ) { if ( Sieve [ i ] == true ) { prime . push_back ( i ) ; for ( int j = i * i ; j <= lmt ; j += i ) { Sieve [ j ] = false ; } } } } vector < bool > SegmentedSieveFn ( int low , int high ) { int lmt = floor ( sqrt ( high ) ) + 1 ; vector < int > prime ; simpleSieve ( lmt , prime ) ; int n = high - low + 1 ; vector < bool > segmentedSieve ( n + 1 , true ) ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) { int lowLim = floor ( low / prime [ i ] ) * prime [ i ] ; if ( lowLim < low ) { lowLim += prime [ i ] ; } for ( int j = lowLim ; j <= high ; j += prime [ i ] ) { if ( j != prime [ i ] ) { segmentedSieve [ j - low ] = false ; } } } return segmentedSieve ; } int countPairsWhoseSumPrimeL_R ( int L , int R ) { vector < bool > segmentedSieve = SegmentedSieveFn ( L , R ) ; int cntPairs = 0 ; for ( int i = L ; i <= R ; i ++ ) { if ( segmentedSieve [ i - L ] ) { cntPairs += i / 2 ; } } return cntPairs ; } int main ( ) { int L = 1 , R = 5 ; cout << countPairsWhoseSumPrimeL_R ( L , R ) ; return 0 ; }