蓝桥杯第十届国B 质数拆分

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017+2=2019 视为同一种方法。

方法：动态规划（0-1背包问题）

这个问题可以转化为 0-1背包问题：

• 背包容量 = 2019

• 物品 = 所有小于 2019 的质数（每个质数只能选或不选）

• 目标：求恰好装满背包的组合数

#include<iostream>
#include<cmath>
using namespace std;#define int long long int a[2020];
int dp[2020];  //dp[j]表示和为j的组合数 bool prime(int x)
{if(x<2) return 0;if(x==2) return 1;for(int i=2; i<=sqrt(x); ++i){if(x%i==0) return 0;}return 1;
}signed main()
{int cnt = 0;  //记录质数的数量 for(int i=2; i<=2019; ++i){if(prime(i)){a[cnt] = i;cnt++;}}dp[0] = 1;  //初始条件：和为0的组合数为1for(int i=0; i<cnt; ++i){for(int j=2019; j>=a[i]; j--){dp[j] += dp[j - a[i]];} }cout<<dp[2019];return 0;
}