题目：

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.这题就是一个完全背包问题，与不同的是，它算的是本质不同的质数和表达式的数目。基准条件return1.，边界return0。求子问题之和的问题。

2.求出一个质数表。

代码：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;


long long mem[100][250];//使用从第x个质数开始的质数（即 primes[x], primes[x+1], ..., primes[len-1]）

组合出和为SP的不同方法总数
int primes[100];
int len = 0;

// 质数判断函数
bool is_prime(int x)
{
	if(x < 2)
	return false;
	if(x == 2)
	return true;
	for(int i = 2 ; i <= sqrt(x) ; i++)
	{
		if(x % i == 0)
		return false;
	}
	return true;
}

// 记忆化搜索函数
long long dfs(int x, int SP) 
{
	long long res = 0;
    if (SP == 0)
	 return 1;
    if (SP < 0 || x >= len)
	 return 0;
    if (mem[x][SP] != -1)
	 return mem[x][SP];
	 
    if (SP >= primes[x])
	{
        res = dfs(x, SP - primes[x]) + dfs(x + 1, SP);
    }
    else
	{
     res = dfs(x + 1, SP);	
	} 
    
    return mem[x][SP] = res;
}

int main() 
{
    // 生成所有200以内的质数
    for(int i = 2; i <= 200; i++)
	 {
        if(is_prime(i)) 
		{
            primes[len++] = i;
        }
    }
    
    int n;
    while(cin >> n)
	{
        memset(mem, -1, sizeof(mem));
        cout << dfs(0, n) << endl;
    }
    
    return 0;
}

dp1:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

long long f[100][250]; 
int primes[100];        
int len = 0;           
// 质数判断函数
bool is_prime(int x) 
{
    if(x < 2) return false;
    if(x == 2) return true;
    for(int i = 2; i <= sqrt(x); i++) 
	{
        if(x % i == 0) return false;
    }
    return true;
}
int main() {
    // 生成所有200以内的质数
    for(int i = 2; i <= 200; i++) 
	{
        if(is_prime(i))
		 {
            primes[++len] = i;
        }
    }
    int n;
    while(cin >> n) 
	{
        memset(f, 0, sizeof(f));  
        f[0][0] = 1;  
        for(int i = 1; i <= len; i++)
		 {
            for(int j = 0; j <= n; j++) 
			{

                if(j >= primes[i]) 
				{
                    f[i][j] = f[i-1][j] + f[i][j - primes[i]];
                }
                else
                f[i][j] = f[i-1][j]; 
            }
        }
        
        cout << f[len][n] << endl;  // 输出结果
    }
    return 0;
}

dp2:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

long long f[100][250]; 
int primes[100];        
int len = 0;           
// 质数判断函数
bool is_prime(int x) 
{
    if(x < 2) return false;
    if(x == 2) return true;
    for(int i = 2; i <= sqrt(x); i++) 
	{
        if(x % i == 0) return false;
    }
    return true;
}
int main() {
    // 生成所有200以内的质数
    for(int i = 2; i <= 200; i++) 
	{
        if(is_prime(i))
		 {
            primes[++len] = i;
        }
    }
    int n;
    while(cin >> n) 
	{
        memset(f, 0, sizeof(f));  
        f[len + 1][0] = 1;
         for(int i = len; i >= 1; i--)
		 {
            for(int j = 0; j <= n; j++) 
			{

                if(j >= primes[i]) 
				{
                    f[i][j] = f[i+1][j] + f[i][j - primes[i]];
                }
                else
                f[i][j] = f[i+1][j]; 
            }
        }
        cout << f[1][n] << endl;  // 输出结果
    }
    return 0;
}