P2563[AHOI2001] 质数和分解

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

2
200

样例输出 #1

1
9845164

题意

一个数要拆成若干质数和，拆分方案不能重复，如 7 = 2+5 = 2+3+2

思路

• 可以直接递归搜索，但是一定要注意避免重复，比如：7=2+5=2+3+2 但是3+4就不行！
• 类似完全背包会更好做，一个背包容量选则若干个物品，只是区别在于这里的满足背包容量即装满，不需要求最大值而是求所有的装法。
  物品2，3，5，7，11，13，，，，筛选法求出所有质数
  然后背包容量1-100。

参考代码

#include <bits/stdc++.h>
using namespace std;
int prime[200];

//prime[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199};
bool pan(int x)
{
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0) return 0;
    return 1;
}
int main()
	{
		//处理质数的数组
		int num=0,n;
        for(int i=2;i<=200;i++)
            if(pan(i))
                prime[++num]=i;      
		while(cin>>n)
			{	 
				int dp[242]={1};
				for(int i=1;i<=num;i++)
					{
						for(int j=prime[i];j<=200;j++)
						{
//							if(j==5) cout<<"i:"<<i<<dp[j]<<"新的："<<dp[j-prime[i]]<<endl; 
							dp[j]+=dp[j-prime[i]];
						}
					}
				cout<<dp[n]<<endl;
			}
		return 0;
	}