Count prime numbers up to N that can be represented as a sum of two prime numbers | C ++ program 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( int n , bool prime [ ] ) { prime [ 0 ] = 0 ; prime [ 1 ] = 0 ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) { prime [ i ] = false ; } } } } void countPrime ( int n ) { bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( n , prime ) ; int dp [ n + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { dp [ i ] += dp [ i - 1 ] ; if ( prime [ i ] == 1 && prime [ i - 2 ] == 1 ) { dp [ i ] ++ ; } } cout << dp [ n ] ; } int main ( ) { int N = 6 ; countPrime ( N ) ; return 0 ; }