1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 int prime[40]; 7 int c1[151]; 8 int c2[151]; 9 int num[151]; 10 int l; 11 void init() 12 { 13 int i,j; 14 num[0]=1; 15 num[1]=1; 16 for(i=2; i<=150; i++) 17 for(j=i*i; j<=150; j+=i) 18 num[j]=1; 19 for(i=2; i<=150; i++) 20 if(!num[i]) 21 prime[l++]=i; //素数表。。 22 } 23 int main() 24 { 25 init(); 26 int n,t,i,j,k; 27 memset(c2,0,sizeof(c2)); 28 for(i=0; i<=150; i+=2) //第一个素数是2，所以这里的增量是2. 29 c1[i]=1; 30 for(i=1; i<=34; i++) 31 { 32 for(j=0; j<=150; j++) 33 { 34 for(k=0; k+j<=150; k+=prime[i]) //每次的添加都是第i个素数的值。 35 c2[k+j]+=c1[j]; 36 } 37 for(j=0; j<151; j++) 38 { 39 c1[j]=c2[j]; 40 c2[j]=0; 41 //printf("%d ",c1[j]); 42 } 43 } 44 cin>>t; 45 while(t--) 46 { 47 cin>>n; 48 cout<<c1[n]<<endl; 49 } 50 return 0; 51 }