Count pairs from a given range whose sum is a Prime Number in that range | 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
function simpleSieve ( lmt , prime ) { let Sieve = new Array ( lmt + 1 ) ; Sieve . fill ( true ) Sieve [ 0 ] = Sieve [ 1 ] = false ; for ( let i = 2 ; i <= lmt ; ++ i ) { if ( Sieve [ i ] == true ) { prime . push ( i ) ; for ( let j = i * i ; j <= lmt ; j += i ) { Sieve [ j ] = false ; } } } } function SegmentedSieveFn ( low , high ) { let lmt = Math . floor ( Math . sqrt ( high ) ) + 1 ; let prime = new Array ( ) ; simpleSieve ( lmt , prime ) ; let n = high - low + 1 ; let segmentedSieve = new Array ( n + 1 ) . fill ( true ) ; for ( let i = 0 ; i < prime . length ; i ++ ) { let lowLim = Math . floor ( low / prime [ i ] ) * prime [ i ] ; if ( lowLim < low ) { lowLim += prime [ i ] ; } for ( let j = lowLim ; j <= high ; j += prime [ i ] ) { if ( j != prime [ i ] ) { segmentedSieve [ j - low ] = false ; } } } return segmentedSieve ; } function countPairsWhoseSumPrimeL_R ( L , R ) { let segmentedSieve = SegmentedSieveFn ( L , R ) ; let cntPairs = 0 ; for ( let i = L ; i <= R ; i ++ ) { if ( segmentedSieve [ i - L ] ) { cntPairs += Math . floor ( i / 2 ) ; } } return cntPairs ; } let L = 1 , R = 5 ; document . write ( countPairsWhoseSumPrimeL_R ( L , R ) ) ;