1213 – Sum of Different Primes

A Dynamic Programming problem.
Simply, you combine primes — which you generated one way or another — that add up to the input. This combination should be executed via Dynamic Programming. Your state consists of:

• n – the number that needs decomposition.
• k – the number of primes n should be divided into.
• i – the lowest prime number that can be used in the next decomposition. This is to avoid repeated primes in the sum.

Your transitions from S(n, k, i) are:

• S(n – prime[i], k – 1, i + 1) – subtract the current prime.
• S(n, k, i + 1) – bypass it.

C++ implementation:

#include <iostream>
#include <cstring>
using namespace std;

#define N 2048
#define P 309
#define K 16

long long nWays[N][K][P], prime[P];

void sieve() {
	int nPrime = 0, isPrime[N];
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = true;
	for (int i = 2; i < N; ++i)
		if (isPrime[i] && (prime[nPrime++] = i))
			for (int j = i * i; j < N; j += i)
				isPrime[j] = false;
}

long long getNWays(int n, int k, int i) {
	if (n == 0 && k == 0)
		return 1;
	if (n < 0 || k < 0 || prime[i] > n || i == P)
		return 0;
	if (nWays[n][k][i] != -1)
		return nWays[n][k][i];
	return nWays[n][k][i] = getNWays(n - prime[i], k - 1, i + 1) + getNWays(n, k, i + 1);
}

int main() {
	// init
	sieve();
	memset(nWays, -1, sizeof nWays);
	// solve
	int n, k;
	while (cin >> n >> k && (n || k))
		cout << getNWays(n, k, 0) << endl;
	return 0;
}