P1832 A+B Problem（再升级）

7

3

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define lli long long int 
 6 using namespace std;
 7 const int MAXN=100001;
 8 lli vis[MAXN];
 9 lli dp[MAXN];
10 int main()
11 {
12     lli n,q;
13     cin>>n;
14     dp[0]=1;
15     vis[1]=1;
16     for(lli i=2;i<=sqrt(n);i++)
17     {
18         if(vis[i]==0)
19         for(lli j=i*i;j<=n;j=j+i)
20             vis[j]=1;
21     }
22     for(lli i=2;i<=n;i++)
23         if(vis[i]==0)
24             for(lli j=i;j<=n;j++)    
25                 dp[j]+=dp[j-i];    
26     cout<<dp[n];
27     return 0;
28 }