【题解-洛谷】P2563 [AHOI2001] 质数和分解

题目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 79252232233327。这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。试编程求解自然数n nn可以写成多少种本质不同的质数和表达式。输入格式文件中的每一行存放一个自然数n ( 2 ≤ n ≤ 200 ) n(2 \leq n \leq 200)n(2≤n≤200)。输出格式依次输出每一个自然数n nn的本质不同的质数和表达式的数目。输入输出样例 #1输入 #12 200输出 #11 9845164代码1朴素二维数组#includebits/stdc.husingnamespacestd;constintN20010;intv[N],n,V,f[N][N],cnt;boolisprime(intx){for(inti2;ix/i;i)if(x%i0)returnfalse;returntrue;}intmain(){while(cinV){cnt0;for(inti2;iV;i){if(isprime(i)){cnt;v[cnt]i;}}ncnt;memset(f,0,sizeoff);f[0][0]1;for(inti1;in;i)for(intj0;jV;j)for(intk0;k*v[i]j;k)f[i][j]f[i-1][j-k*v[i]];coutf[n][V]endl;}return0;}代码2优化1二维数组#includebits/stdc.husingnamespacestd;constintN20010;intv[N],n,V,f[N][N],cnt;boolisprime(intx){for(inti2;ix/i;i)if(x%i0)returnfalse;returntrue;}intmain(){while(cinV){cnt0;for(inti2;iV;i){if(isprime(i)){cnt;v[cnt]i;}}ncnt;memset(f,0,sizeoff);f[0][0]1;for(inti1;in;i)for(intj0;jV;j){f[i][j]f[i-1][j];if(v[i]j)f[i][j]f[i][j-v[i]];}coutf[n][V]endl;}return0;}代码3一维数组#includebits/stdc.husingnamespacestd;constintN20010;intv[N],n,V,f[N],cnt;boolisprime(intx){for(inti2;ix/i;i)if(x%i0)returnfalse;returntrue;}intmain(){while(cinV){cnt0;for(inti2;iV;i){if(isprime(i)){cnt;v[cnt]i;}}ncnt;memset(f,0,sizeoff);f[0]1;for(inti1;in;i)for(intjv[i];jV;j){f[j]f[j-v[i]];}coutf[V]endl;}return0;}结果