hdu 2189 dp

 1 /*
 2 类似完全背包，容量为n的背包用素数填，求满背包的种数
 3 dp(i,j)表示用不超过i的素数组成的j的种数
 4 dp[i][j]=dp[i-1][j],若i为素数则dp[i][j]+=dp[i][j-i]
 5 */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 using namespace std;
10 
11 const int maxn=155;
12 int prime[maxn],flag[maxn],num;
13 int dp[maxn][maxn];
14 
15 void getprimes()
16 {
17     num=0;memset(flag,1,sizeof(flag));
18     for(int i=2;i<=maxn;i++)
19     {
20         if(flag[i]) prime[num++]=i;
21         for(int j=0;j<=num && prime[j]*i<maxn;j++)
22         {
23             flag[prime[j]*i]=false;
24             if(i%prime[j]==0) break;
25         }
26     }
27 }
28 
29 int main()
30 {
31     getprimes();
32     int t,n,i,j,ans;
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d",&n);
37         memset(dp,0,sizeof(dp));
38         dp[1][0]=1;
39         for(i=2;i<=n;i++)
40         {
41             for(j=0;j<=n;j++)
42                 dp[i][j]=dp[i-1][j];
43             if(!flag[i]) continue;
44             for(j=i;j<=n;j++)
45                 dp[i][j]+=dp[i][j-i];
46         }
47         printf("%d
",dp[n][n]);
48     }
49     return 0;
50 }