Count of primes below N which can be expressed as the sum of two primes | Python3 implementation of the approach ; Function for Sieve of Eratosthenes ; False here indicates that it is not prime ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to return the count of primes less than or equal to n which can be expressed as the sum of two primes ; To store the required count ; If the integer is prime and it can be expressed as the sum of 2 and a prime number ; Driver code
MAX = 100005 NEW_LINE prime = [ True for i in range ( MAX ) ] NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE for p in range ( MAX ) : NEW_LINE INDENT if ( p * p > MAX ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( prime [ p ] ) : NEW_LINE INDENT for i in range ( 2 * p , MAX , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def countPrimes ( n ) : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE cnt = 0 NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT if ( prime [ i ] and prime [ i - 2 ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT return cnt NEW_LINE DEDENT n = 11 NEW_LINE print ( countPrimes ( n ) ) NEW_LINE