Count of primes below N which can be expressed as the sum of two primes | Java 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
class GFG { static int MAX = 100005 ; static boolean [ ] prime = new boolean [ MAX ] ; static void SieveOfEratosthenes ( ) { for ( int i = 0 ; i < MAX ; i ++ ) prime [ i ] = true ; prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p < MAX ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i < MAX ; i += p ) prime [ i ] = false ; } } } static int countPrimes ( int n ) { SieveOfEratosthenes ( ) ; int cnt = 0 ; for ( int i = 2 ; i < n ; i ++ ) { if ( prime [ i ] && prime [ i - 2 ] ) cnt ++ ; } return cnt ; } public static void main ( String [ ] args ) { int n = 11 ; System . out . print ( countPrimes ( n ) ) ; } }