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\n",dp[n][n]);48     }49     return 0;50 }