Count prime numbers up to N that can be represented as a sum of two prime numbers | Java approach for the above approach ; Function to store all prime numbers up to N using Sieve of Eratosthenes ; Set 0 and 1 as non - prime ; If p is prime ; Set all multiples of p as non - prime ; Function to count prime numbers up to N that can be represented as the sum of two prime numbers ; Stores all the prime numbers ; Update the prime array ; Create a dp array of size n + 1 ; Update dp [ 1 ] = 0 ; Iterate over the range [ 2 , N ] ; Add the previous count value ; Increment dp [ i ] by 1 if i and ( i - 2 ) are both prime ; Print the result ; Driver Code
class GFG { static void SieveOfEratosthenes ( int n , boolean prime [ ] ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) { prime [ i ] = false ; } } } } static void countPrime ( int n ) { boolean prime [ ] = new boolean [ n + 1 ] ; for ( int i = 0 ; i < prime . length ; i ++ ) { prime [ i ] = true ; } SieveOfEratosthenes ( n , prime ) ; int dp [ ] = new int [ n + 1 ] ; for ( int i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = 0 ; } dp [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { dp [ i ] += dp [ i - 1 ] ; if ( prime [ i ] == true && prime [ i - 2 ] == true ) { dp [ i ] ++ ; } } System . out . print ( dp [ n ] ) ; } public static void main ( String [ ] args ) { int N = 6 ; countPrime ( N ) ; } }