Number of distinct ways to represent a number as sum of K unique primes | Java 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
import java . io . * ; import java . util . * ; class GFG { static ArrayList < Integer > prime = new ArrayList < Integer > ( ) ; static boolean [ ] isprime = new boolean [ 1000 ] ; static int [ ] [ ] [ ] dp = new int [ 200 ] [ 20 ] [ 1000 ] ; static void sieve ( ) { for ( int i = 0 ; i < 1000 ; i ++ ) isprime [ i ] = true ; 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 . add ( i ) ; } } } static int CountWays ( int i , int j , int sum , int n , int k ) { if ( i >= prime . size ( ) - 1 sum > n ) { return 0 ; } if ( sum == n ) { if ( j == k ) { return 1 ; } return 0 ; } if ( j == k ) return 0 ; if ( dp [ i ] [ j ] [ sum ] != 0 ) return dp [ i ] [ j ] [ sum ] ; int inc = 0 , exc = 0 ; inc = CountWays ( i + 1 , j + 1 , sum + prime . get ( i ) , n , k ) ; exc = CountWays ( i + 1 , j , sum , n , k ) ; return dp [ i ] [ j ] [ sum ] = inc + exc ; } public static void main ( String [ ] args ) { sieve ( ) ; int N = 100 , K = 5 ; System . out . println ( CountWays ( 0 , 0 , 0 , N , K ) ) ; } }