1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #define N 1010 7 #define LL __int64 8 using namespace std; 9 10 LL dp[N];11 12 int prim[N],np;13 bool isprime[N];14 15 void init(){16     np=0;17     memset(isprime,true,sizeof(isprime));18     for(int i=2;i<N;i++){19         if(isprime[i]){20             prim[++np]=i;21             for(int j=i*i;j<N;j+=i)22             isprime[j]=false;23         }24     }25 }26 27 int main(){28     init();29     int n,tmp;30     while(scanf("%d",&n)!=EOF){31         for(int i=0;i<=n;i++)32         dp[i]=1LL;33         bool flag=false;34         for(int k=1;k<=np;k++){35             if(prim[k]>n) break;36             for(int i=n;i>=0;i--){37                 tmp=prim[k];38                 while(i-tmp>=0){39                     dp[i]+=dp[i-tmp];40                     tmp*=prim[k];41                 }42             }43         }44         printf("%I64d\n",dp[n]);45     }46     return 0;47 }