题目传送门

解题思路:

先搞一遍欧拉筛,然后f[i]表示i的答案,对于1~n的所有素数,都大于其的数的f改一下.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 long long n,p[1001],vis[1001],tot,f[1001];
 8 
 9 inline void oulashai() {
10     memset(vis,1,sizeof(vis));
11     vis[0] = vis[1] = 0;
12     for(int i = 2;i <= n; i++) {
13         if(vis[i]) p[++tot] = i; 
14         for(int j = 1;j <= tot; j++) {
15             if(i * p[j] > n) break;
16             vis[i*p[j]] = 0;
17             if(i % p[j] == 0) break;
18         }
19     }
20 }
21 
22 int main() {
23     scanf("%lld",&n);
24     oulashai();
25     f[0] = 1;
26     for(int i = 1;i <= tot; i++)
27         for(int j = p[i];j <= n; j++) 
28             f[j] += f[j-p[i]];
29     printf("%lld",f[n]);
30     return 0;
31 }