洛谷 P1304 哥德巴赫猜想——一个律师的信件，和 283 年的接力

牙擦

826人浏览 · 2026-09-03 16:50:40

牙擦 · 2026-09-03 16:50:40 发布

洛谷 P1304 哥德巴赫猜想——一个律师的信件，和 283 年的接力

📌 摘要

P1304 要求验证 4∼N 的所有偶数能否写成两质数之和，输出第一个加数最小的方案。核心算法只有两步：判断质数 + 暴力枚举。但这道题背后是一个 283 年未解的数学猜想——1742 年一个律师给欧拉写了封信，欧拉回信说"我信，但我证不出来"。本文从哥德巴赫的故事讲起，到伪代码题解，再延伸到埃氏筛与欧拉筛——从"判一个数是不是质数"到"筛出一群质数"的效率进化。

题目链接：P1304 哥德巴赫猜想

📝 前言

这篇题解没有源代码，只有伪代码。

作为一名信奥教练，我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了，脑子没跑通。下次遇到变体题，还是不会。

伪代码剥掉了语言的壳，只留算法的骨架。你看不到 #include，看不到 cin、cout，看不到那些让你以为"我会了"的语法细节。你能看到的只有：这一步做什么、下一步做什么、为什么这么做。

如果你是路过的友友，已经在这道题上挣扎了很久——先去喝杯水，回来重新看看自己卡在哪一步。是没读懂题意？是思路方向偏了？还是代码有 bug 但逻辑其实对？大多数时候不是不会，是走偏了。偏了不可怕，可怕的是偏了之后直接放弃，去抄一份能 AC 的代码。抄完你以为你懂了，其实你只是搬了别人的结论。

除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说，能理解。但平时练习，给自己一点耐心。先自己想、自己写、自己调，跑不过了再来看伪代码：你的思路和这里差在哪一步。那一步，就是你真正学到的东西。

这道题尤其值得自己想。因为它背后的故事，比代码本身精彩得多。

📜 哥德巴赫与他的猜想

✉️ 1742 年的一封信

1742 年 6 月 7 日，莫斯科。

一个叫克里斯蒂安·哥德巴赫（Christian Goldbach）的人给远在柏林的莱昂哈德·欧拉写了一封信。信里讨论的是数论问题——整数的性质、质数的分布。

哥德巴赫不是职业数学家。他学的是法律和哲学，在圣彼得堡科学院当过历史学教授和数学秘书，后来到莫斯科外交部任职。但他对数字有极好的直觉，和欧拉长期通信讨论数学问题。在科学史上，业余爱好者做出重要贡献的例子不少——哥德巴赫就是其中之一。

在 6 月 7 日那封信的页边空白处，他写下了这样一句话（拉丁文，欧拉用的语言）：

任意一个大于 2 的整数，都可以写成三个质数之和。

当时的数学家把 1 也算作质数。如果按现代定义（1 不是质数），哥德巴赫的原话拆成两条：

弱猜想：任意大于 5 的奇数 = 三个质数之和。
强猜想：任意大于 2 的偶数 = 两个质数之和。

6 月 30 日，欧拉回信。他说了一段在数学史上被反复引用的话：

“I am certain that this is entirely true, but I cannot prove it.”

我坚信这是一个完全正确的定理，但我无法证明它。

—— 莱昂哈德·欧拉，1742 年 6 月 30 日，致哥德巴赫的回信（Goldbach’s conjecture — Wikipedia）

欧拉是 18 世纪最伟大的数学家，3000 多篇论文、886 部著作。连他都证不出来的东西，分量可想而知。

两个人都没意识到，这封信页边的一行字，会成为数论中最著名的未解难题之一——哥德巴赫猜想。

🏆 陈景润与"1+2"

欧拉之后，一百多年没人动得了这个猜想。不是没人试，是数学工具不够——质数的分布太不规则，传统的分析方法触不到它的核心。

转折发生在 20 世纪。一群数学家发明了一种新工具：筛法。筛法的思路很朴素——不是直接证明"每个偶数都能拆成两质数"，而是先证明"每个偶数都能拆成两个’差不多是质数’的数"，然后一步步收紧"差不多"的范围。

术语	含义	对应猜想
9+9	两个数各不超过 9 个质因数	1920 布伦
7+7 → 6+6 → 5+5 → …	逐步收紧	1920s–1940s
1+4	一个质数 + 一个不超过 4 质因数的数	1965 王元、潘承洞
1+3	一个质数 + 一个不超过 3 质因数的数	1965 潘承洞
1+2	一个质数 + 一个不超过 2 质因数的数	1966 陈景润

1966 年，一个叫陈景润的中国人在《科学通报》上发表了两页摘要，宣布证明了"1+2"：每个充分大的偶数 = 1 个质数 + 1 个不超过 2 个质因数的数（Chen’s theorem — Wikipedia）。

两页摘要。没有完整证明。

整个国际数学界将信将疑。一个从未在西方期刊发表过论文的中国数学家，声称做到了当时筛法的最强结果？

1973 年，陈景润在《中国科学》发表了完整证明（陈景润《大偶数表为一个素数及一个不超过二个素数的乘积之和》, 1973）。论文长逾百页，中间用了一种改进的筛法——后来被称为加权筛法。证明读起来极其艰难，但逻辑无懈可击。

国际数学界震动。"1+2"被命名为陈氏定理（Chen’s Theorem）。1978 年，陈景润获全国科学大会奖，后来又获国家自然科学一等奖。

一个中国人，在哥德巴赫猜想的接力赛上，把接力棒推到了离终点最近的位置。

从"1+2"到"1+1"（即强猜想本身），这最后一步至今没有迈过去。

📅 283 年接力时间线

年份	人物	事件
1742.06.07	哥德巴赫	给欧拉写信，提出猜想
1742.06.30	欧拉	回信：信其为真，但无法证明
1900	希尔伯特	将猜想相关的问题列入 23 大数学问题（第 8 问题）
1920	布伦	用筛法证明"9+9"，筛法正式登场
1937	维诺格拉多夫	证明弱猜想（充分大的奇数 = 3 质数之和）
1957	王元	证明"2+3"
1965	潘承洞、王元	各自证明"1+4"和"1+3"
1966	陈景润	证明"1+2"，发表摘要于《科学通报》
1973	陈景润	发表完整证明于《中国科学》
2013	Helfgott	完整证明弱猜想（不需要"充分大"限制）（Helfgott’s proof — Wikipedia）
2012–至今	Oliveira e Silva 等	计算机验证强猜想至 4×10¹⁸（Goldbach conjecture verification）
至今	—	强猜想仍未证明

283 年。从一封信的页边空白处，到 4×10¹⁸ 次计算机验证。每一步验证都是对的——没有找到一个反例。但"没有找到反例"不等于"证明"。这就是数学：一万个例子不够，一亿个不够，4×10¹⁸ 个也不够。你需要的是逻辑，不是枚举。

而这道洛谷题——P1304——让你做的恰恰是枚举。用代码验证小范围内的猜想。你写不出证明，但你能写出验证。这本身就是一件有意思的事。

🔍 题目在考什么

输入偶数 N，对 4 到 N 的每个偶数 e，找到两个质数 p₁、p₂ 使得 e = p₁ + p₂，且 p₁ 是所有满足条件的方案中最小的。

两个要求：

判断质数：需要知道一个数是不是质数。
找最小方案：从 2 开始枚举第一个加数，找到的第一组合法解就是答案。

数据范围 N≤10000，O(N²) 的暴力枚举完全可行，不需要筛法优化。但"判断质数"这件事本身，可以从 O(N) 优化到 O(√N) 再到 O(1)（预筛）——这就是延伸部分要讲的。

💡 解题思路

对每个偶数 e（从 4 到 N，步长 2）：

从 j=2 开始枚举，如果 j 是质数，计算 b = e - j
如果 b 也是质数，这就是答案（因为 j 从小到大枚举，第一个找到的方案 j 最小）
输出 e=j+b

核心是一个 isPrime 函数。最朴素的写法：从 2 试到 num-1，如果某个数能整除 num，num 不是质数。这是 O(N) 的判断，对每个偶数的每次枚举都要调用——总复杂度 O(N² × √N) 量级，但 N=10000 时依然能过。

📝 伪代码

函数 isPrime(num):
    如果 num == 2: 返回 true
    令 i = 2
    当 i < num:
        如果 num 能被 i 整除: 返回 false
        否则: i = i + 1
    返回 true

主程序:
    读取 N
    对 e = 4, 6, 8, ..., N:           // 遍历每个偶数
        对 j = 2, 3, ..., e-1:         // 枚举第一个加数
            如果 isPrime(j):
                b = e - j
                如果 isPrime(b):
                    输出 "e = j + b"
                    跳出内层循环       // 找到最小方案，不再继续

代码中的细节

代码里有一个声明了但未使用的数组 primeNumber[N]——注释写着"处理出 n 之前的所有质数"，但实际上没有预筛，而是每次调用 isPrime 实时判断。这说明作者最初考虑过预筛方案（用筛法先算出质数表），最终选择了更简单的实时试除。

isPrime 函数从 i=2 试到 i=num-1，可以优化为只试到 √num——因为如果 num 有一个大于 √num 的因子，它必然也有一个小于 √num 的因子。但朴素写法对 N=10000 足够过题。

🎯 关键点

第一个加数最小。 题目要求输出"第一个加数最小"的方案。代码的做法是：j 从 2 开始递增枚举，找到的第一个 isPrime(j) && isPrime(e-j) 的组合就是答案——因为 j 越小，第一个加数越小。这是一个"贪心"思想：从小到大试，第一个合法的就是最优。

用样例 N=10 追踪：

偶数 e	尝试 j	isPrime(j)?	b=e-j	isPrime(b)?	输出
4	2	是	2	是	4=2+2
6	2	是	4	否	—
6	3	是	3	是	6=3+3
8	2	是	6	否	—
8	3	是	5	是	8=3+5
10	2	是	8	否	—
10	3	是	7	是	10=3+7

注意 10=5+5 也成立，但 3+7 先被找到（j=3 < j=5），所以输出 3+7。

isPrime 的优化空间。 当前从 2 试到 num-1，复杂度 O(num)。优化到试到 √num，复杂度降为 O(√num)。对 num=9973（10000 以内最大的质数），试除法从 9972 次减到 99 次——快 100 倍。更进一步的优化是预筛质数表，判质数变成 O(1)。详见延伸部分。

10=3+7=5+5，为什么不输出 5+5？ 因为 j 从 2 递增，j=3 时就找到 7 是质数，直接 break 了，根本轮不到 j=5。“第一个找到的就是最小的”——这是从小到大枚举的自然结果，不需要额外排序。

⚠️ 注意事项

VLA（变长数组）警告：代码中 int primeNumber[n] 使用了变长数组，这是 C99 特性，不是标准 C++。部分编译器（如 MSVC）不支持。虽然在本题中没有实际使用这个数组，但竞赛中应避免 VLA，改用 const int MAXN = 10005; int primeNumber[MAXN];。
isPrime 的效率：从 2 试到 num-1 是最朴素写法。可优化为试到 √num（i * i <= num），效率提升约 √N 倍。N=10000 时不影响 AC，但养成优化习惯很重要。
偶数步长：外层循环 i += 2 是对的——只处理偶数。如果写成 i++ 会多处理奇数，虽然不影响正确性但浪费时间。
bits/stdc++.h：万能头文件在竞赛中方便，但不是标准 C++，部分环境不可用。正式项目应替换为具体头文件。

🌳 延伸：质数筛——从试除到线性

P1304 的核心是"判断质数"。判一个数是不是质数，有三种做法，效率递增。当题目变成"找出 N 以内所有质数"时——也就是筛法——效率差距更加明显。

🔨 试除法

最朴素的做法。对每个数 n，从 2 试到 √n，看有没有因子。

函数 isPrime(n):
    如果 n < 2: 返回 false
    令 i = 2
    当 i × i ≤ n:
        如果 n 能被 i 整除: 返回 false
        i = i + 1
    返回 true

判一个数：O(√n)。
判 N 以内所有数：O(N√N)。

对 N=10000：10000 × 100 = 10⁶ 次操作，毫无压力。对 N=10⁷：10⁷ × 3162 ≈ 3×10¹⁰ 次，TLE。

试除法的优势是不需要预处理——给一个数判一次。适合"判单个数"或"判少量数"的场景。P1304 就属于这种：最多 10000 个偶数，每个最多试 10000 次，总量 10⁸，勉强能过。但如果 N 更大，就需要筛法了。

📊 埃氏筛

埃拉托斯特尼筛法（Sieve of Eratosthenes），公元前 200 多年希腊数学家发明的。

思路极简：从 2 开始，每找到一个质数，就把它的所有倍数标记为合数。

筛法（埃氏筛）:
    初始化 isPrime[2..N] 全为 true
    令 i = 2
    当 i × i ≤ N:
        如果 isPrime[i] 为 true:
            // i 是质数，标记 i 的所有倍数为合数
            令 j = i × i            // 从 i² 开始，更小的倍数已被更小的质数筛掉
            当 j ≤ N:
                isPrime[j] = false
                j = j + i           // 步长 = i，跳到下一个倍数
        i = i + 1

为什么从 i² 开始？ 因为 i×2, i×3, …, i×(i-1) 已经被 2, 3, …, (i-1) 这些更小的质数筛过了。比如 i=5 时，5×2=10 已被 2 筛掉，5×3=15 已被 3 筛掉，5×4=20 已被 2 筛掉。所以从 5×5=25 开始才有意义。

埃氏筛的效率：O(N log log N)。这比 O(N√N) 快太多了——log log N 是一个增长极慢的函数，N=10⁷ 时 log log N ≈ 3，几乎可以看作 O(N)。

但埃氏筛有一个问题：重复标记。 看 30 这个数：

质数	操作	是否标记 30
2	标记 4, 6, 8, 10, …, 30, …	是（30 = 2×15）
3	标记 9, 12, 15, …, 30, …	是（30 = 3×10）
5	标记 25, 30, 35, …	是（30 = 5×6）

30 被标记了 3 次。每个合数有几个不同的质因数，就被标记几次。这就是埃氏筛做不到严格线性的原因（Sieve of Eratosthenes — Wikipedia）。

⚡ 欧拉筛（线性筛）

欧拉筛（也叫线性筛、Euler’s Sieve）解决的就是"重复标记"问题。核心思想：每个合数只被它的最小质因数标记一次。

筛法（欧拉筛）:
    初始化 isPrime[2..N] 全为 true
    质数表 primes = 空列表

    对 i = 2 到 N:
        如果 isPrime[i] 为 true:
            将 i 加入 primes            // i 是质数

        对 primes 中的每个 p（从小到大）:
            如果 i × p > N: 跳出循环    // 超出范围
            标记 isPrime[i × p] = false // i×p 是合数，被 p 筛掉
            如果 i 能被 p 整除: 跳出循环  // 关键！

最后那行"如果 i 能被 p 整除就 break"是整个算法的灵魂。

为什么？因为如果 i 能被 p 整除，说明 p 是 i 的最小质因数（因为 p 是从小到大枚举的）。那么 i×p’（p’ > p）这个合数的最小质因数是 p，不是 p’——所以它应该由 p 来筛，不应该由 p’ 来筛。如果不 break，后面更大的 p’ 会重复标记，就退化成埃氏筛了。

举个例子，i=4：

p	i×p	标记	4%p==0?	操作
2	8	isPrime[8]=false	是	break！

i=4，p=2 时标记 8，然后 4%2==0，break。为什么不继续用 p=3 标记 4×3=12？因为 12 = 4×3 = 2×2×3 = 2×6，它的最小质因数是 2。当 i=6 时，p=2 会标记 6×2=12——那时候 12 才被正确地筛掉。

这就是"每个合数只被最小质因数筛一次"的实现机制（Sieve of Eratosthenes — Wikipedia）。

用 N=20 追踪完整的欧拉筛过程：

i	isPrime[i]?	primes（处理后）	标记的合数	break原因
2	true→质数	[2]	2×2=4	2%2==0 → break
3	true→质数	[2,3]	3×2=6, 3×3=9	3%3==0 → break
4	false	[2,3]	4×2=8	4%2==0 → break
5	true→质数	[2,3,5]	5×2=10, 5×3=15, 5×5=25>20	5%5==0 → break
6	false	[2,3,5]	6×2=12	6%2==0 → break
7	true→质数	[2,3,5,7]	7×2=14, 7×3=21>20	7%7==0 → break
8	false	[2,3,5,7]	8×2=16	8%2==0 → break
9	false	[2,3,5,7]	9×2=18, 9×3=27>20	9%3==0 → break
10	false	[2,3,5,7]	10×2=20	10%2==0 → break
11~20	按需	…	…	…

最终质数表：[2, 3, 5, 7, 11, 13, 17, 19]。每个合数只被标记了一次——8 被 2 标记，12 被 2 标记，15 被 3 标记，16 被 2 标记，18 被 2 标记，20 被 2 标记。没有重复。

⚖️ 三种方法对比

	试除法	埃氏筛	欧拉筛
判单个数	O(√n)	O(1)（预筛后查表）	O(1)（预筛后查表）
筛 N 以内所有质数	O(N√N)	O(N log log N)	O(N)
空间	O(1)	O(N)	O(N) + 质数表
是否重复标记	不适用	是	否
预处理	不需要	需要	需要
适用场景	判少量数 / N 小	N 中等，写法简单	N 大，需要严格线性
N=10⁷ 的耗时	≈3×10¹⁰（TLE）	≈10⁷×3 ≈ 3×10⁷（AC）	≈10⁷（AC，更快）
P1304 是否需要	足够（N≤10000）	杀鸡用牛刀	杀鸡用牛刀

P1304 不需要筛法。 N≤10000，试除法完全够用。但知道筛法存在、知道它的原理、知道在什么时候该从试除法切换到筛法——这是从入门到进阶的分界线。下次遇到 N=10⁷ 的题，你就知道试除法不够了，得换工具。

这和哥德巴赫猜想的故事是同一个道理：工具决定了你能走多远。 布伦的筛法证明了"9+9"，陈景润的加权筛法证明了"1+2"。你今天学的埃氏筛和欧拉筛，是同一棵进化树上更靠根的节点——但方向是一致的：用更高效的工具，处理更大规模的问题。

📚 延伸阅读文献

论文与文献

陈景润. 大偶数表为一个素数及一个不超过二个素数的乘积之和. 《中国科学》数学专辑, 1973: 111–128. （Chen’s theorem — Wikipedia） —— “1+2” 的完整证明，陈氏定理的原始文献。
H. A. Helfgott. The ternary Goldbach conjecture is true. arXiv:1312.7748, 2013. （Goldbach’s weak conjecture — Wikipedia） —— 弱哥德巴赫猜想的完整证明。
T. Oliveira e Silva, S. Herzog, S. Pardi. Empirical verification of the even Goldbach conjecture, and computation of the prime-counting function, up to 4×10¹⁸. Mathematics of Computation, 83(287): 2033–2060, 2014. （Goldbach’s conjecture — Wikipedia） —— 强猜想的计算机验证记录。
D. Hilbert. Mathematische Probleme (Mathematical Problems). Bulletin of the AMS, 8(10):437–479, 1902. （Hilbert’s problems — Wikipedia） —— 哥德巴赫猜想被纳入第 8 问题。

在线资源

洛谷. P1304 哥德巴赫猜想. https://www.luogu.com.cn/problem/P1304
Goldbach’s conjecture — Wikipedia. https://en.wikipedia.org/wiki/Goldbach’s_conjecture —— 哥德巴赫猜想的最全面参考。
Sieve of Eratosthenes — Wikipedia. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes —— 埃氏筛与欧拉筛的百科条目。