质数拆分

将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017 + 2 = 2019视为同一种方法。

思路

• 隐藏条件(坑点)：当一个数本身就是质数时，算一种方法
• 问题转化为：输入一个数 $n$，求出 $[2,n]$ 之间的所有质数，然后在这些质数中任选 $k$ 个质数，使这 $k$ 个质数的和为 $n$，求不同的选取方法数
• 如果真的要与“组合数”扯上关系的话，那么复杂度就太高了，为了尽量降低复杂度，用动态规划比较好

动态规划1：

• 建一个二维DP数组 $dp[][]$ ，注意方法数可能很大，所以这个数组应该用 $longlong$ 类型
• 该数组的一个维度为 $[2,n]$ 的质数编号，一个维度为 $[0,n]$ 下标
• DP数组 $dp[i][j]$的含义为在前 $i$个质数中，能组成 $j$的最大方法数
• $dp[0][0]=1$

优化：

• 将二维数组压缩为一维数组$dp[]$
• $dp[0]=1$

代码如下

/*** 输入一个数n(不能太大)，求这个数被拆分为若干个两两不同的质数之和的方法数*/
#include <iostream>
#include <vector>
#define ll long long
using namespace std;vector<int> prime_num;  //质数数组
int t;                  //质数数组的大小
vector<vector<ll>> dp;  // DP数组
int N;                  //输入的N//朴素的判断一个数是不是质数的方法
bool is_prime(int n) {for (int i = 2; i * i <= n; i++) {if (n % i == 0) return false;}return true;
}//准备[2,n]之间的质数
void init() {scanf("%d", &N);prime_num.push_back(0);  //质数下标从1开始for (int i = 2; i < N; i++) {if (is_prime(i)) {prime_num.push_back(i);}}t = (int)prime_num.size();dp.resize(t);for (int i = 0; i < t; i++) {dp[i].resize(N + 1);}
}void solve() {dp[0][0] = 1;for (int i = 1; i < t; i++) {for (int j = 0; j <= N; j++) {//先假设选这个数之后不能组成j，则“继承”上一个的方法数dp[i][j] = dp[i - 1][j];//如果判断发现能组成，则加上之前的方法数if (j >= prime_num[i]) {dp[i][j] += dp[i - 1][j - prime_num[i]];}}}printf("%lld\n", dp[t - 1][N]);/** 优化代码，其对应的初始省略*/// dp[0] = 1;// for (int i = 1; i < t; i++) {//     for (int j = N; j >= prime_num[i]; j--) {//         dp[j] += dp[j - prime_num[i]];//     }// }// printf("%lld\n", dp[N]);
}int main(void) {init();solve();return 0;
}