Count pairs from a given range whose sum is a Prime Number in that range | Python 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 ) ; 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
import math NEW_LINE def simpleSieve ( lmt , prime ) : NEW_LINE INDENT Sieve = [ True ] * ( lmt + 1 ) NEW_LINE Sieve [ 0 ] = Sieve [ 1 ] = False NEW_LINE for i in range ( 2 , lmt + 1 ) : NEW_LINE INDENT if ( Sieve [ i ] == True ) : NEW_LINE INDENT prime . append ( i ) NEW_LINE for j in range ( i * i , int ( math . sqrt ( lmt ) ) + 1 , i ) : NEW_LINE INDENT Sieve [ j ] = false NEW_LINE DEDENT DEDENT DEDENT return prime NEW_LINE DEDENT def SegmentedSieveFn ( low , high ) : NEW_LINE INDENT lmt = int ( math . sqrt ( high ) ) + 1 NEW_LINE prime = [ ] NEW_LINE prime = simpleSieve ( lmt , prime ) NEW_LINE n = high - low + 1 NEW_LINE segmentedSieve = [ True ] * ( n + 1 ) NEW_LINE for i in range ( 0 , len ( prime ) ) : NEW_LINE INDENT lowLim = int ( low // prime [ i ] ) * prime [ i ] NEW_LINE if ( lowLim < low ) : NEW_LINE INDENT lowLim += prime [ i ] NEW_LINE for j in range ( lowLim , high + 1 , prime [ i ] ) : NEW_LINE INDENT if ( j != prime [ i ] ) : NEW_LINE INDENT segmentedSieve [ j - low ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT return segmentedSieve NEW_LINE DEDENT def countPairsWhoseSumPrimeL_R ( L , R ) : NEW_LINE INDENT segmentedSieve = SegmentedSieveFn ( L , R ) NEW_LINE cntPairs = 0 NEW_LINE for i in range ( L , R + 1 ) : NEW_LINE INDENT if ( segmentedSieve [ i - L ] == True ) : NEW_LINE INDENT cntPairs += i / 2 NEW_LINE DEDENT DEDENT return cntPairs NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = 1 NEW_LINE R = 5 NEW_LINE print ( countPairsWhoseSumPrimeL_R ( L , R ) ) NEW_LINE DEDENT