P2563 [AHOI2001]质数和分解
题目描述
任何大于 1 的自然数 n 都可以写成若干个大于等于 2 且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，9 的质数和表达式就有四种本质不同的形式：
9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 。
这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。
试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。
输入输出格式
输入格式：
文件中的每一行存放一个自然数 n(2 < n < 200) 。
输出格式：
依次输出每一个自然数 n 的本质不同的质数和表达式的数目。
输入输出样例
输入样例#1：
2
200输出样例#1：
1
9845164先生成一个质数表然后用个小背包就可以了
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #define lli long long int
7 using namespace std;
8 void read(lli &n)
9 {
10 char c='+';lli x=0;bool flag=0;
11 while(c<'0'||c>'9')
12 {c=getchar();if(c=='-')flag=1;}
13 while(c>='0'&&c<='9')
14 {x=x*10+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 lli n,m;
18 lli a[10001];
19 lli dp[10001];
20 lli sum[10001];
21 lli vis[10001];
22 int main()
23 {
24 dp[0]=1;
25 vis[1]=1;
26 for(lli i=2;i<=201;i++)
27 if(!vis[i])
28 for(lli j=i*i;j<=301;j+=i)
29 vis[j]=1;
30 for(lli i=2;i<=200;i++)
31 if(vis[i]==0)
32 for(lli j=i;j<=200;j++)
33 dp[j]=dp[j-i]+dp[j];
34 while(scanf("%d",&n)==1)
35 {
36 printf("%lld\n",dp[n]);
37 }
38 return 0;
39 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-07-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
