企业官网建设流程全解析

题目：P2563 [AHOI2001] 质数和分解

题目描述

任何大于1 11的自然数n nn都可以写成若干个大于等于2 22且小于等于n nn的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，9 99的质数和表达式就有四种本质不同的形式：

9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 79=2+5+2=2+3+2+2=3+3+3=2+7。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数n nn可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数n ( 2 ≤ n ≤ 200 ) n(2 \leq n \leq 200)n(2≤n≤200)。

输出格式

依次输出每一个自然数n nn的本质不同的质数和表达式的数目。

输入输出样例 #1

输入 #1

2 200

输出 #1

1 9845164

代码1（朴素，二维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=200+10;intv[N],n,V,f[N][N],cnt;boolisprime(intx){for(inti=2;i<=x/i;i++)if(x%i==0)returnfalse;returntrue;}intmain(){while(cin>>V){cnt=0;for(inti=2;i<=V;i++){if(isprime(i)){cnt++;v[cnt]=i;}}n=cnt;memset(f,0,sizeoff);f[0][0]=1;for(inti=1;i<=n;i++)for(intj=0;j<=V;j++)for(intk=0;k*v[i]<=j;k++)f[i][j]+=f[i-1][j-k*v[i]];cout<<f[n][V]<<endl;}return0;}

代码2（优化1，二维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=200+10;intv[N],n,V,f[N][N],cnt;boolisprime(intx){for(inti=2;i<=x/i;i++)if(x%i==0)returnfalse;returntrue;}intmain(){while(cin>>V){cnt=0;for(inti=2;i<=V;i++){if(isprime(i)){cnt++;v[cnt]=i;}}n=cnt;memset(f,0,sizeoff);f[0][0]=1;for(inti=1;i<=n;i++)for(intj=0;j<=V;j++){f[i][j]=f[i-1][j];if(v[i]<=j)f[i][j]+=f[i][j-v[i]];}cout<<f[n][V]<<endl;}return0;}

代码3（一维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=200+10;intv[N],n,V,f[N],cnt;boolisprime(intx){for(inti=2;i<=x/i;i++)if(x%i==0)returnfalse;returntrue;}intmain(){while(cin>>V){cnt=0;for(inti=2;i<=V;i++){if(isprime(i)){cnt++;v[cnt]=i;}}n=cnt;memset(f,0,sizeoff);f[0]=1;for(inti=1;i<=n;i++)for(intj=v[i];j<=V;j++){f[j]+=f[j-v[i]];}cout<<f[V]<<endl;}return0;}

结果