Number of distinct ways to represent a number as sum of K unique primes | Prime vector ; Sieve array of prime ; DP array ; 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 ; Precompute primes by sieve
var prime = [ ] ; var isprime = Array ( 1000 ) . fill ( true ) ; var dp = Array . from ( Array ( 200 ) , ( ) => Array ( 20 ) ) ; for ( var i = 0 ; i < 200 ; i ++ ) for ( var j = 0 ; j < 20 ; j ++ ) dp [ i ] [ j ] = new Array ( 1000 ) . fill ( 0 ) ; function sieve ( ) { for ( var i = 2 ; i * i <= 1000 ; i ++ ) { if ( isprime [ i ] ) { for ( var j = i * i ; j <= 1000 ; j += i ) { isprime [ j ] = false ; } } } for ( var i = 2 ; i <= 1000 ; i ++ ) { if ( isprime [ i ] ) { prime . push ( i ) ; } } } function CountWays ( i , j , sum , n , k ) { if ( i > prime . length 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 ] ; var 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 ; } sieve ( ) ; var N = 100 , K = 5 ; document . write ( CountWays ( 0 , 0 , 0 , N , K ) ) ;