Uva1213（线性筛模板+dp）

题意：

把n拆成k个不同素数的和，有多少种拆法。

解法：

打表后dp即可，这个dp的问题可以归纳为：在n个数中选k个数，使得和m的方案数

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 bool visit[10100000];
 6 int prime[10000000];
 7 int f[1130][200];
 8 
 9 int prime_num = 0;
10 void generate_prim(int n) {
11     memset(visit, true, sizeof(visit));
12     for (int i = 2; i <= n; ++i) {
13         if (visit[i] == true) prime[++prime_num] = i;    
14         for (int j = 1; ((j <= prime_num) && (i * prime[j] <= n)); ++j) {
15             visit[i * prime[j]] = false;
16             if (i % prime[j] == 0) break;
17         }
18     }
19     return;
20 }
21 
22 void generate_plan() {
23     generate_prim(1300);
24     f[0][0] = 1;
25     for (int k= 0; k < prime_num; k++) {
26         for (int i = 1120; i >= 0; i--) {
27             int UP = lower_bound(prime, prime + k, i) - prime + 1;
28             for (int j = 1; j < UP; j++) {
29                 if (prime[k] > i)break;
30                 f[i][j] += f[i - prime[k]][j - 1];
31             }
32         }
33     }
34     return;
35 }
36 
37 int main() {
38     generate_plan();
39     int n, m; 
40     while (scanf("%d%d", &n, &m) && n&&m) {
41         printf("%d
", f[n][m]);
42     }
43     return 0;
44 }