哥德巴赫猜想

题意

输入偶数 N，对 4,6,8,...,N 中的每个偶数，输出它写成两个质数之和的一种方案。若有多种方案，要求第一个加数最小。

思路

先用埃氏筛预处理 0..N 的质数表 is_prime。

对每个偶数 even，从小到大枚举第一个加数 first，令：

text

1second = even - first

如果 first 和 second 都是质数，就输出这一组并停止枚举。因为 first 是从小到大枚举的，所以第一次找到的方案就是第一个加数最小的方案。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：用 range(4, n+1, 2) 可以按步长枚举偶数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：质数相关判断适合用整数运算。
列表 is_prime[x] 可以作为快速查询表。
f-string f"{even}={first}+{second}" 适合按题目格式输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22def build_prime_table(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = False
    is_prime[1] = False

    for x in range(2, limit + 1):
        if is_prime[x]:
            for multiple in range(x * x, limit + 1, x):
                is_prime[multiple] = False

    return is_prime


n = int(input())
is_prime = build_prime_table(n)

for even in range(4, n + 1, 2):
    for first in range(2, even):
        second = even - first
        if is_prime[first] and is_prime[second]:
            print(f"{even}={first}+{second}")
            break

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

bool is_prime[10005]; // 质数表
int n;

// 埃氏筛法预处理质数表
void sieve(int limit) {
    fill(is_prime, is_prime + limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= limit; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }
}

int main() {
    cin >> n;
    sieve(n);
    for (int even = 4; even <= n; even += 2) { // 枚举偶数
        for (int first = 2; first < even; first++) {
            int second = even - first;
            if (is_prime[first] && is_prime[second]) {
                cout << even << "=" << first << "+" << second << "\n";
                break; // 找到第一个加数最小的方案
            }
        }
    }
    return 0;
}

复杂度

埃氏筛复杂度约为 $O(N \log\log N)$ 。之后对每个偶数枚举加数，最坏 $O(N^2)$ ，但 N <= 10000 可以通过。空间复杂度是 $O(N)$ 。

总结

需要反复判断质数时，先预处理质数表。要求“第一个加数最小”时，从小到大枚举并在第一次成功时停止。

目录

题意

思路

Python 知识

代码

复杂度

总结