一、先把题目变成一个“小侦探故事” 假设老师给小明一个数字10问10 可以由多少种不同的“两个素数之和”组成我们知道10 3 7 10 5 5所以答案是2而且3 7 7 3是按照同一种方法。题目明确规定只有两个分解方案中的素数集合不同才算不同方案。所以我们不能把3 7 7 3算成两次。二、这道题真正问的是什么我们可以把问题浓缩成一句话给你一个偶数 n找出所有满足p q n的素数对(p,q)而且每一对只能计算一次。例如n 10尝试2 8 3 7 4 6 5 5其中2 是素数但 8 不是 ❌3 是素数7 也是素数 ✅4 不是素数 ❌5 是素数5 也是素数 ✅所以10 3 7 10 5 5答案2三、第一关什么是素数⭐一个大于 1 的整数只能被 1 和它自己整除就是素数。例如2 √ 3 √ 4 × 5 √ 6 × 7 √ 8 × 9 × 10 × 11 √所以2 3 5 7 11都是素数。四、如果一个一个判断素数可以吗当然可以。比如我们枚举2 3 4 5 ... n/2然后判断i 是不是素数 n-i 是不是素数如果两个都是素数ans;就可以了。但是问题来了如果 n 很大呢如果每次都重新判断一个数是不是素数就可能重复做大量工作。所以这道题的漂亮解法是⭐ 先把所有素数一次性找出来这就是埃氏筛——筛素数五、埃氏筛像筛面粉一样筛掉合数我们准备一个数组bool not_prime[1000005];它的含义是not_prime[x] true表示x 不是素数。反过来not_prime[x] false表示x 目前还是“素数候选人”。可以把它想象成 一开始所有数字都参加“素数选拔赛”然后我们不断把合数淘汰掉。六、筛素数第一步1 不是素数程序not_prime[1] true;因为1不是素数。七、从 2 开始检查参考程序for (int i 2; i n; i) { if (!not_prime[i]) { primes[pcnt] i; for (int j 2; i * j n; j) { not_prime[i * j] true; } } }我们一步一步看。八、遇到 2发现 2 是素数因为not_prime[2] false所以2 是素数把它保存primes[pcnt] 2;然后把 2 的倍数全部标记成合数2×2 4 2×3 6 2×4 8 2×5 10 ...于是4 × 6 × 8 × 10 × ...都被淘汰。九、遇到 33 还没有被标记not_prime[3] false所以3 是素数保存primes {2,3}然后把3×2 6 3×3 9 3×4 12 ...标记成合数。十、遇到 4这时候not_prime[4] true说明4 已经被 2 淘汰所以if (!not_prime[i])不成立。直接跳过。十一、最后得到一个“素数通讯录”比如n 20最后primes 2 3 5 7 11 13 17 19这就是我们的素数名单。参考程序就是先通过get_primes()完成这件事情。十二、第二关找到两个素数现在假设n 20我们已经知道2 3 5 7 11 13 17 19都是素数。那么我们要寻找p q 20例如2 18 ❌ 3 17 ✅ 5 15 ❌ 7 13 ✅ 11 9 ❌所以20 3 17 20 7 13答案2十三、为什么只枚举到 n/2这是这道题最重要的一个小技巧。参考程序primes[i] n / 2为什么假设n 20如果我们枚举到11那么20 - 11 9这已经超过一半了。而前面其实已经检查过20 9 11所以再检查11 9就是重复计算。十四、这就是“去重”的秘密 ⭐⭐⭐假设n 10如果我们全部枚举2 8 3 7 4 6 5 5 6 4 7 3 8 2你会发现3 7 7 3重复了。所以我们只检查p n/2也就是p 5只需要2 8 3 7 4 6 5 5这样3 7出现一次。7 3根本不会再出现。这就是一种非常重要的“只枚举一半自动避免重复”十五、程序中这一句非常关键参考程序for (int i 0; i pcnt primes[i] n / 2; i)可以拆成i pcnt表示还没有走完素数数组。以及primes[i] n / 2表示只检查前一半的素数。十六、然后检查另一个数字是不是素数程序if (!not_prime[n - primes[i]]) ans;这句话看起来有点吓人我们翻译成“小学生语言”假设n 20 primes[i] 7那么另一个数字就是20 - 7 13程序检查!not_prime[13]因为13 是素数所以not_prime[13] false那么!false true于是ans;答案加 1。十七、完整走一遍 n 20我们来做一张“侦探表”。第一个素数第二个数20-p是素数吗算不算218❌不算317✅✅515❌不算713✅✅119❌不算所以20 3 17 20 7 13答案2十八、再看一个 n 28素数2 3 5 7 11 13 17 19 23只检查p 14于是2 26 ❌ 3 25 ❌ 5 23 ✅ 7 21 ❌ 11 17 ✅ 13 15 ❌所以28 5 23 28 11 17答案2十九、现在来看完整参考程序参考程序核心结构是先筛素数再枚举不超过n/2的素数并检查n-primes[i]是否也是素数。#include cassert #include cstdio using namespace std; int n, ans; bool not_prime[1000005]; int primes[500000], pcnt 0; void get_primes() { not_prime[1] true; for (int i 2; i n; i) { if (!not_prime[i]) { primes[pcnt] i; for (int j 2; i * j n; j) { not_prime[i * j] true; } } } } int main() { scanf(%d, n); get_primes(); for (int i 0; i pcnt primes[i] n / 2; i) { if (!not_prime[n - primes[i]]) ans; } printf(%d\n, ans); return 0; }二十、把程序分成“三个房间” 其实程序只有三个任务。 房间1输入scanf(%d, n);得到n 房间2制作素数名单get_primes();完成2 3 5 7 11 13 ... 房间3寻找答案for (...) if (...) ans;也就是找到一个素数p再看看n-p是不是素数。二十一、同学们一定要理解的核心思想这道题千万不要只记代码。应该记住下面这个“魔法公式”⭐ 核心公式如果n p q那么q n - p所以枚举一个素数 p只需要检查 n-p 是不是素数。而为了避免p q q p重复只枚举p n/2。二十二、为什么这道题需要“筛素数”假如我们要检查n - p是不是素数。如果每次都从 2 开始试除2 3 4 5 ...会比较慢。于是我们提前做一次埃氏筛把2~n里面所有素数找出来。以后判断not_prime[x]就可以O(1)知道它是不是素数。这就是算法思想中的“先预处理再快速查询”二十三、最容易犯的 4 个错误 ⚠️错误1把pq和qp算两次例如37 73不能算两次。解决办法primes[i] n / 2只枚举一半。错误2忘记 1 不是素数程序not_prime[1] true;就是为了明确告诉计算机1 ❌错误3看到!not_prime就晕记住not_prime[x] true意思x 不是素数。所以!not_prime[x]就是x 是素数。可以把它翻译成“不是非素数”也就是“是素数”错误4只判断 p 是素数例如20看到7是素数就直接ans这是错的。必须同时保证7 是素数 20-713 也是素数两个都成立才能算一种方案。二十四、这道题的“万能思维模板” 以后遇到类似题目可以按照这个顺序思考第一步题目要找什么p q n第二步能不能枚举一个可以。枚举p然后q n-p第三步怎么快速判断 q提前筛素数第四步如何避免重复只枚举p n/2第五步找到一组合法方案怎么办ans;二十五、最后送大家一句“考场口诀” 先筛素数名单做好枚举一半避免重复q n-p两个都素找到一组答案加一