1. 问题引入当“质数”遇上“背包”最近在复盘蓝桥杯的历年真题特别是国赛B组的题目发现2019年的这道“质数拆分”很有意思。它表面上是一个关于质数的数学问题但稍微深入一想就会发现其内核是一个经典的动态规划问题——01背包。很多同学第一次看到题目可能会有点懵不知道从何下手或者写出来的代码效率极低只能通过部分样例。今天我就结合自己刷题和教学的经验把这道题的解题思路、代码实现以及背后的优化技巧掰开揉碎了讲清楚。题目的大意是将2019拆分成若干个互不相同的质数之和问一共有多少种不同的拆分方法。注意这里“互不相同”和“质数”是两个关键约束。比如232014就不是合法拆分因为2014不是质数222015也不是因为质数重复了。这题直接暴力枚举所有质数组合是不可行的。2019以内的质数有几百个所有子集的数量是天文数字。所以我们必须转换思路。既然是要从一堆质数物品中选取若干个每个最多选一次使得它们的和总重量恰好等于2019背包容量并且求的是方案数这不就是恰好装满背包的方案数问题吗而且每个质数只能选一次正是01背包的模型。接下来我们就分几步走先解决质数从哪里来的问题素数筛选再厘清如何套用01背包模型来计算方案数最后给出完整的、优化的C/C代码实现。我会重点解释为什么要这样做以及在编码过程中有哪些容易踩的坑。2. 基石高效获取质数列表素数筛选我们的“物品”是2019以内的所有质数。第一步就是要把这些质数高效、无误地找出来。这里我强烈推荐使用埃拉托斯特尼筛法也就是常说的“埃氏筛”。对于2019这个数量级它完全够用且实现简单不易出错。2.1 为什么选择埃氏筛你可能听说过更快的“欧拉筛”线性筛。但对于本题埃氏筛足矣理由如下时间复杂度足够埃氏筛的时间复杂度是 O(n log log n)对于 n2019这个计算量微乎其微在竞赛的时限内可以忽略不计。实现简单代码逻辑清晰不容易在紧张的比赛环境中写错。相比之下欧拉筛需要多维护一个质数表边界条件稍微复杂一点。空间换时间我们只需要一个布尔型数组来标记是否为质数空间复杂度 O(n)完全可接受。我们的目标是生成一个质数列表primes并且知道质数的个数cnt以便后续进行背包计算。2.2 埃氏筛的实现细节与易错点下面给出标准的埃氏筛实现并附上关键注释#include vector using namespace std; const int MAXN 2020; // 比2019稍大一点 bool isPrime[MAXN]; vectorint primes; void sieve() { // 1. 初始化假设所有数都是质数 fill(isPrime, isPrime MAXN, true); isPrime[0] isPrime[1] false; // 0和1不是质数 // 2. 核心筛选过程 for (int i 2; i MAXN; i) { if (isPrime[i]) { // i是质数将其加入列表 primes.push_back(i); // 标记i的所有倍数为非质数 // 从 i*i 开始标记是常见的优化避免重复标记 // 但这里i最大也就2019i*i可能溢出int所以保险起见可以从ii开始 for (int j i * 2; j MAXN; j i) { isPrime[j] false; } } } }几个需要注意的坑数组大小MAXN至少要是202020191。养成习惯定义全局常量避免魔法数字。初始化务必显式地将isPrime[0]和isPrime[1]设为false。有时我们会忘记1不是质数。内层循环的起始点很多教程写for (int j i * i; j MAXN; j i)。这是一个优化因为小于i*i的合数已经被更小的质数标记过了。但是当i较大时比如i46350时i*i就超过int范围了这会导致溢出成为潜在BUG。在竞赛中如果对数据范围心里没底用j i * 2更安全。本题中i很小用i*i没问题。结果存储我们用vectorint primes来动态存储找到的质数。这比用静态数组再维护一个下标更灵活。最终primes.size()就是质数的个数cnt。执行完sieve()函数后primes向量里就按顺序存放了所有小于2020的质数。我们可以打印一下primes.size()验证2019以内的质数有306个具体数值可能因边界略有差异但算法正确即可。3. 核心转化为01背包方案数问题拿到质数列表后问题就变成了从这cnt个质数物品中选取若干个每个数最多选一次使得它们的和恰好为target2019背包容量求选取的方案数。这正是01背包“恰好装满”求方案数的经典问题。我们可以定义动态规划状态设dp[j]表示考虑前i个质数这个维度在滚动数组优化中被隐藏了能够凑出总和恰好为j的方案数。3.1 状态转移方程推导这是最核心的部分我们一步步推。初始状态当什么物品都不考虑时只有一种方法凑出总和0那就是什么都不选。所以dp[0] 1。对于其他容量j 0在没开始选物品时是不可能凑出的所以初始化为dp[j] 0。状态转移当我们逐个考虑质数primes[i]相当于物品其“重量”和“价值”都是它本身的值时对于每个目标总和j从大到小遍历这是01背包滚动数组优化的关键有两种选择不选当前质数那么方案数继承自考虑前i-1个质数时凑出j的方案数也就是上一轮的dp[j]。选当前质数前提是j primes[i]。如果选了当前质数那么剩下的总和就是j - primes[i]需要由前i-1个质数来凑。所以方案数是上一轮中dp[j - primes[i]]。因此新的dp[j]考虑完当前质数后等于旧的dp[j]不选当前质数加上dp[j - primes[i]]选当前质数。用伪代码表示就是dp[j] dp[j] dp[j - primes[i]];(当j primes[i])注意这里的dp[j]在等号右边是“旧”值考虑前i-1个物品的状态等号左边是更新后的“新”值。由于我们使用一维数组并从后向前遍历j可以确保在计算dp[j]时dp[j - primes[i]]还没有被当前物品更新过它代表的是“旧”状态完美符合01背包的要求。3.2 一维滚动数组优化详解为什么j要从target遍历到primes[i]这是理解01背包优化的关键。 如果我们从j primes[i]遍历到target那么在计算较大的j时dp[j - primes[i]]可能已经被当前质数primes[i]更新过了。这意味着我们可能重复使用了同一个质数即一个质数被用了多次这就变成了“完全背包”问题违反了“每个质数最多用一次”的条件。 而从后向前遍历可以保证在更新dp[j]时dp[j - primes[i]]对应的状态是还没有考虑过当前质数primes[i]的状态从而保证了每个质数只被使用一次。过程模拟假设质数列表前几个是[2, 3, 5]target5。 初始化dp [1, 0, 0, 0, 0, 0](下标0到5)。考虑质数2(weight2)j5:dp[5] dp[5] dp[3] 0 0 0j4:dp[4] dp[4] dp[2] 0 0 0j3:dp[3] dp[3] dp[1] 0 0 0j2:dp[2] dp[2] dp[0] 0 1 1(找到一种方案只选2) 此时dp [1, 0, 1, 0, 0, 0]考虑质数3(weight3)j5:dp[5] dp[5] dp[2] 0 1 1(找到方案23)j4:dp[4] dp[4] dp[1] 0 0 0j3:dp[3] dp[3] dp[0] 0 1 1(找到方案只选3) 此时dp [1, 0, 1, 1, 0, 1]考虑质数5(weight5)j5:dp[5] dp[5] dp[0] 1 1 2(找到新方案只选5。总方案数23 和 5) 最终dp[5] 2。可以看到最终dp[target]就是我们想要的答案。4. 代码实现与逐行解析将素数筛选和动态规划结合起来以下是完整的C代码。我使用long long类型来存储方案数因为结果可能很大防止溢出。#include iostream #include vector #include cstring // 用于memset或fill using namespace std; const int MAXN 2020; // 筛法范围上限 const int TARGET 2019; // 目标和 bool isPrime[MAXN]; // 筛法标记数组 vectorint primes; // 存储所有质数 long long dp[TARGET 1]; // dp数组dp[j]表示凑出j的方案数 // 埃拉托斯特尼筛法 void sieve() { fill(isPrime, isPrime MAXN, true); // 使用fill初始化 isPrime[0] isPrime[1] false; for (int i 2; i MAXN; i) { if (isPrime[i]) { primes.push_back(i); // 从 i*2 开始标记避免i*i可能导致的溢出问题虽然本题不会 for (int j i * 2; j MAXN; j i) { isPrime[j] false; } } } } int main() { // 步骤1筛出所有需要的质数 sieve(); int cnt primes.size(); // 质数个数 cout The number of primes less than 2020 is: cnt endl; // 可选用于验证 // 步骤2初始化动态规划数组 memset(dp, 0, sizeof(dp)); // 将所有方案数初始化为0 dp[0] 1; // 和为0的方案数为1什么都不选 // 步骤3动态规划01背包核心 for (int i 0; i cnt; i) { // 遍历每个质数物品 int weight primes[i]; // 当前质数的大小既是“重量”也是“价值” if (weight TARGET) { // 一个小优化如果当前质数已经大于目标后面的更大直接跳出循环 // 注意这个优化不是必须的因为内层循环条件 j weight 已经保证了不会处理。 // 但这里break可以节省外层循环次数。 break; } // 01背包滚动数组优化从后向前遍历 for (int j TARGET; j weight; --j) { dp[j] dp[j - weight]; // 状态转移方程 } } // 步骤4输出结果 cout The number of ways to split 2019 into distinct primes is: dp[TARGET] endl; return 0; }关键代码解析与注意事项dp数组的数据类型long long是必须的。尽管题目没给答案范围但这类组合计数问题结果很容易超出int范围。使用long long是最保险的做法。初始化dp[0] 1这是整个动态规划的“起点”代表了空集的方案。如果设成0那么所有结果都将是0。内层循环的遍历顺序for (int j TARGET; j weight; --j)这是灵魂所在。务必是从大到小遍历才能保证每个质数只被使用一次。这是01背包最易错的点之一。状态转移dp[j] dp[j - weight];非常简洁。它等价于dp[j] dp[j] dp[j - weight];含义是“凑出总和j的方案数”等于“不选当前质数的方案数”加上“选了当前质数后凑出剩余部分j-weight的方案数”。关于weight TARGET的优化在遍历质数时如果当前质数已经大于2019它不可能参与构成和为2019的正数组合所以可以提前结束循环。这是一个有效的剪枝。不过由于我们的质数表本身是递增的一旦有一个质数大于2019后面的所有质数都大于2019所以用break跳出整个质数遍历循环是安全的能节省时间。5. 测试验证与结果分析运行上面的程序你会得到输出结果。为了验证我们程序的正确性我们可以进行一些小规模测试。测试用例设计边界测试target很小比如target2。小于2的质数只有2。那么方案数应该是1吗不注意dp[0]1代表不选任何数也是一种方案和为0。对于target2只有质数2可用。dp[2]会从dp[0]转移过来结果为1。这对应方案{2}。结果是合理的。简单测试target5。我们手动推导过质数有{2,3,5}。方案有{5}和{2,3}两种。程序应该输出2。中等测试target10。可用的质数有{2,3,5,7}。可以枚举一下{2,3,5}{3,7}{2,3,5}和{3,7}是仅有的两组吗还有{2,5,3}是重复的。等等{5,5}不行重复且5只能用一次{2,8}不行8不是质数。{2,2,3,3}也不行重复。{7,3}和{3,7}是同一种。所以确实是2种。我们可以修改代码中的TARGET为10来验证。题目最终测试target2019。运行程序得到最终答案。这里我就不直接公布答案了留给读者自己运行验证。这是一个确定的整数。如何验证结果的合理性即使不知道标准答案检查质数表打印出primes的前后一些元素看是否正确。比如第一个质数应该是2最后一个小于2019的质数应该是2017。检查dp数组中间状态对于较小的target如20可以打印出整个dp数组手动验证几个值。逻辑自洽确保算法每一步的逻辑是清晰的。素数筛正确 - 01背包模型正确状态、初始化、转移、遍历顺序- 结果自然可信。算法对比可以用另一种思路比如DFS搜索剪枝对于小数据来验证小规模数据的结果是否一致。6. 常见错误与深度思考在解这道题或者类似题目时下面这些坑点需要特别注意6.1 关于“互不相同”的理解与实现题目要求“互不相同的质数”在我们的模型里是如何保证的在“物品”层面我们的质数列表primes本身是通过筛法得到的每个质数只出现一次。这保证了“质数”的互异性。在“选择”层面01背包的“每个物品最多选一次”的特性天然保证了我们不会重复选取同一个质数。这是通过内层循环从大到小遍历来实现的。如果从小到大遍历就变成了完全背包一个质数可以被选无限次那就错了。所以“互不相同”这个条件被我们的模型完美处理了不需要额外代码。6.2 初始化dp[0] 1的深刻含义这是动态规划求方案数问题的常见技巧但初学者容易困惑。dp[0]1代表“凑出总和为0的方案有1种”即“什么都不选”。为什么需要它 考虑我们第一个质数weight2。当我们要计算dp[2]凑出2的方案数时状态转移是dp[2] dp[2] dp[0]。这里的dp[0]就代表了“选择当前这个质数2然后剩下的总和为0”的方案数。剩下的总和为0只有一种方式就是什么都不再选了。所以dp[0]1使得“选择当前物品”这个分支的贡献能被正确计算。 如果没有这个初始化dp[0]0那么dp[2]永远会是0因为“选择2”这个分支的贡献是0导致所有方案数都无法被正确累加。6.3 数据范围与溢出问题这是竞赛中非常实际的问题。质数个数2019以内的质数大约300个cnt用int足够。dp数组下标最大到2019用int索引足够。方案数dp[target]这是最容易出错的地方将2019拆分成不同质数的方案数这个值可能非常大。int类型通常最大值约21亿很可能存不下。所以dp数组必须使用long long类型在C中通常至少是64位最大值约9e18。这是必须养成的习惯对于计数类DP只要不是特别确定范围很小就用long long。6.4 算法扩展与变种思考这道题是“恰好装满”的01背包方案数问题。我们可以思考几个变种“至少/至多”装满如果题目改成“和至少为2019的方案数”或“和不超过2019的方案数”状态定义和初始化就需要调整。求具体方案如果不仅要数方案数还要输出所有具体的拆分方式那么DP数组就需要存储路径信息或者改用深度优先搜索(DFS)加剪枝。但那样复杂度会很高可能只适用于较小的target。质数可以重复使用这就变成了完全背包问题。只需要把内层循环的遍历顺序从j--改为j即可。更大的target如果target非常大比如10^5质数个数也会增多约n/ln(n)个。我们的算法时间复杂度是 O(cnt * target)空间是 O(target)。对于10^5的数量级时间复杂度在10^10量级可能会超时。这时就需要更优化的算法或数学方法比如生成函数这已经超出了本题范围但知道这个边界很重要。6.5 调试技巧如果在编写此类题目时遇到问题可以缩小规模把TARGET改成10或20打印出每一步的dp数组与手动计算对比。验证素数筛单独运行筛法函数打印出质数列表检查是否正确。检查遍历顺序再次确认内层循环是逆序 (j--)。这是01背包和完全背包的根本区别。检查数据类型确认dp数组是long long并且输出格式匹配 (%lld或cout)。7. 总结与举一反三回顾这道“质数拆分”题它的价值在于将一个看似是数论的问题通过建模巧妙地转化为一个标准的动态规划问题。这种“问题转化”的能力在算法竞赛和实际编程中至关重要。解题思维链路可以总结为识别约束“质数” - 需要素数筛“互不相同” - 暗示每个数最多选一次。抽象模型“选取若干个数和固定” - 背包问题“每个数最多选一次” - 01背包“求方案数” - DP状态存储方案数。设计算法埃氏筛获取物品列表 - 01背包DP求方案数。注意细节dp[0]1初始化j的逆序遍历防重复long long防溢出。举一反三很多问题都有类似的套路硬币找零问题给定不同面额的硬币每种无限多或不限凑成某个金额的方案数。这是完全背包问题。子集和问题给定一个数组是否存在一个子集的和为target。这是01背包的布尔值版本。组合总和IVLeetCode 377给定一个数组数字可重复使用凑成target的排列数。这需要改变遍历顺序。最后在竞赛中遇到这类题编码速度很重要。建议将素数筛和01背包模板化熟记于心。例如可以把埃氏筛写成一个函数把01背包求方案数的部分也封装起来。这样在比赛时就能快速套用把时间留给更复杂的逻辑思考。这道题在正确建模后代码其实非常短核心部分就十几行考验的就是基本功和思维转换能力。