Number of distinct ways to represent a number as sum of K unique primes | Prime list ; 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 ; Driver code ; Precompute primes by sieve
prime = [ ] NEW_LINE isprime = [ True ] * 1000 NEW_LINE dp = [ [ [ '0' for col in range ( 200 ) ] for col in range ( 20 ) ] for row in range ( 1000 ) ] NEW_LINE def sieve ( ) : NEW_LINE INDENT for i in range ( 2 , 1000 ) : NEW_LINE INDENT if ( isprime [ i ] ) : NEW_LINE INDENT for j in range ( i * i , 1000 , i ) : NEW_LINE INDENT isprime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT for i in range ( 2 , 1000 ) : NEW_LINE INDENT if ( isprime [ i ] ) : NEW_LINE INDENT prime . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def CountWays ( i , j , sums , n , k ) : NEW_LINE INDENT if ( i >= len ( prime ) or sums > n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( sums == n ) : NEW_LINE INDENT if ( j == k ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if j == k : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ i ] [ j ] [ sums ] == 0 : NEW_LINE INDENT return dp [ i ] [ j ] [ sums ] NEW_LINE DEDENT inc = 0 NEW_LINE exc = 0 NEW_LINE inc = CountWays ( i + 1 , j + 1 , sums + prime [ i ] , n , k ) NEW_LINE exc = CountWays ( i + 1 , j , sums , n , k ) NEW_LINE dp [ i ] [ j ] [ sums ] = inc + exc NEW_LINE return dp [ i ] [ j ] [ sums ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT sieve ( ) NEW_LINE N = 100 NEW_LINE K = 5 NEW_LINE print ( CountWays ( 0 , 0 , 0 , N , K ) ) NEW_LINE DEDENT