# 題目: UVa 1213 - Sum of Different Primes

# 題目說明

求將K個小於等於N的質數相加後等於N的方法數量

---

INPUT:
每筆測資輸入兩個整數N、K
當N與K為0時結束程式

---

OUTPUT:
輸出dp[N][K]

# 解題方法

先將<=1120的所有質數找出，存入prime

定義一個dp[i][j]
i為當前的N，也就是能取到的最大數字
j為相加的質數數量

dp[i][j] += dp[i - prime[k]][j - 1]
代表將dp[i - prime[k]][j - 1]加上當前的prime[k]
將其所有可能加總，即為dp[i][j]

# 參考程式碼

#include <iostream>
#include <vector>;

using namespace std;

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, K;
	vector<int> prime;
	vector<bool> vis(1121);
	int dp[1121][15] = {};

	// find prime number
	prime.emplace_back(2);
	for (int i = 3; i <= 1120; i += 2) if (!vis[i])
	{
		prime.emplace_back(i);
		for (int j = i * 2; j <= 1120; j += i) vis[j] = true;
	}

	// dp (knapsack)
	dp[0][0] = 1;
	for (int k = 0; k < prime.size(); ++k) for (int i = 1120; i >= prime[k]; --i)
		for (int j = 14; j >= 1; --j) dp[i][j] += dp[i - prime[k]][j - 1];

	while (cin >> N >> K, N && K) cout << dp[N][K] << "\n";

	return 0;
}

# 參考資料

https://github.com/morris821028/UVa/blob/master/volume012/1213%20-%20Sum%20of%20Different%20Primes.c
https://blog.csdn.net/mobius_strip/article/details/73657860