摘要：
D（i，j）表示i个素数的和是j的方案数，则D（i，j）=sigmad，其中p[k]表示第k个素数。注意，递归顺序是向后的，否则将计算重复。代码中第二和第三个循环的顺序是可互换的。vis[i]）素数[cnt++]=i；18} 1920voidp（）21{22d[0][0]=1；23for24用于//的j个素数25的和是k26d[j][k]+=d[j-1][k-prime[i]]；27}2829intmain（）30{31//freopen；32Init（）；33dp（）；34intk，n；35whileprintf；3637return0；38}代码：
题意：
选择K个质数使它们的和为N，求总的方案数。
分析：
虽然知道推出来了转移方程， 但还是没把代码敲出来，可能基本功还是不够吧。
d(i, j)表示i个素数的和为j的方案数，则 d(i, j) = sigma d(i-1, j-p[k]) ，其中p[k]表示第k个素数
注意递推的顺序是倒着推的，否则会计算重复的情况。
代码中第二重和第三重循环的顺序可互换。
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxp = 190; 5 const int maxn = 1120; 6 int cnt = 0; 7 int prime[maxp]; 8 bool vis[maxn + 10]; 9 10 int d[15][maxn + 10]; 11 12 void Init() 13 { 14 int m = sqrt(maxn + 0.5); 15 for(int i = 2; i <= m; ++i) if(!vis[i]) 16 for(int j = i * i; j <= maxn; j += i) vis[j] = true; 17 for(int i = 2; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i; 18 } 19 20 void dp() 21 { 22 d[0][0] = 1; 23 for(int i = 0; i < cnt; ++i) 24 for(int j = 14; j > 0; --j) //j个质数的和 25 for(int k = maxn; k >= prime[i]; --k) //为k 26 d[j][k] += d[j-1][k-prime[i]]; 27 } 28 29 int main() 30 { 31 //freopen("in.txt", "r", stdin); 32 Init(); 33 dp(); 34 int k, n; 35 while(scanf("%d%d", &n, &k) == 2 && n) printf("%d ", d[k][n]); 36 37 return 0; 38 }