Number of distinct ways to represent a number as sum of K unique primes | C ++ program to count the Number of distinct ways to represent a number as K different primes ; Prime vector ; Sieve array of prime ; DP array ; Initialise all numbers as prime ; Sieve of Eratosthenes . ; Push all the primes into prime vector ; Function to get the number of distinct ways to get sum as K different primes ; If index went out of prime array size or the sum became larger than n return 0 ; If sum becomes equal to n and j becomes exactly equal to k . Return 1 , else if j is still not equal to k , return 0 ; If sum != n and still j as exceeded , return 0 ; If that state is already calculated , return directly the ans ; Include the current prime ; Exclude the current prime ; Return by memoizing the ans ; Driver code ; Precompute primes by sieve
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > prime ; bool isprime [ 1000 ] ; int dp [ 200 ] [ 20 ] [ 1000 ] ; void sieve ( ) { memset ( isprime , true , sizeof ( isprime ) ) ; for ( int i = 2 ; i * i <= 1000 ; i ++ ) { if ( isprime [ i ] ) { for ( int j = i * i ; j <= 1000 ; j += i ) { isprime [ j ] = false ; } } } for ( int i = 2 ; i <= 1000 ; i ++ ) { if ( isprime [ i ] ) { prime . push_back ( i ) ; } } } int CountWays ( int i , int j , int sum , int n , int k ) { if ( i > prime . size ( ) sum > n ) { return 0 ; } if ( sum == n ) { if ( j == k ) { return 1 ; } return 0 ; } if ( j == k ) return 0 ; if ( dp [ i ] [ j ] [ sum ] ) return dp [ i ] [ j ] [ sum ] ; int inc = 0 , exc = 0 ; inc = CountWays ( i + 1 , j + 1 , sum + prime [ i ] , n , k ) ; exc = CountWays ( i + 1 , j , sum , n , k ) ; return dp [ i ] [ j ] [ sum ] = inc + exc ; } int main ( ) { sieve ( ) ; int N = 100 , K = 5 ; cout << CountWays ( 0 , 0 , 0 , N , K ) ; }