1 #include<iostream> 2 using namespace std; 3 int n; 4 const int maxn=1012; 5 bool note[maxn+1]; 6 long long p[maxn]; 7 long long dp[maxn][maxn]; 8 long long tot; 9 int pre() 10 { 11 for(int i=2;i<=n;i++) 12 { 13 if(!note[i]) 14 { 15 p[++tot]=i; 16 } 17 for(int j=1;j<=tot&&i*p[j]<=n;j++) 18 { 19 note[i*p[j]]=1; 20 if(i%p[j]==0) 21 { 22 break; 23 } 24 } 25 } 26 } 27 int main() 28 { 29 cin>>n; 30 pre(); 31 for(int i=0;i<=tot;i++) 32 { 33 dp[i][0]=1; 34 } 35 for(int i=1;i<=n;i++) 36 { 37 dp[0][i]=1; 38 } 39 for(int i=1;i<=tot;i++) 40 { 41 for(int j=1;j<=n;j++) 42 { 43 dp[i][j]=dp[i-1][j]; 44 for(int k=p[i];k<=j;k*=p[i]) 45 { 46 dp[i][j]+=dp[i-1][j-k]; 47 } 48 } 49 } 50 cout<<dp[tot][n]<<endl; 51 return 0; 52 }
https://blog.csdn.net/wyfcyx_forever/article/details/40211739