哥德巴赫猜想

题目描述

对 $6$ 到 $100$ 的每个偶数 $n$ ，输出一行 n=p+q，其中 $p$ 、 $q$ 均为素数，且 $p$ 取所有合法拆分中最小的那一个。

思路

先用埃氏筛一次性标好 $100$ 以内的素数表。然后对每个偶数 $n$ ，从 $3$ 开始按奇数升序枚举第一个加数 $p$ ， $q=n-p$ ，找到第一个 $p$ 、 $q$ 都是素数的组合即可。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-29 21:16
# update_at: 2026-09-29 21:16

LIMIT = 100  # 题目只拆 6~100 的偶数


def sieve(limit: int) -> list[bool]:
    """埃氏筛：is_prime[x] 为 True 表示 x 是素数。"""
    is_prime = [False, False] + [True] * (limit - 1)
    for p in range(2, int(limit ** 0.5) + 1):
        if is_prime[p]:
            is_prime[p * p::p] = [False] * ((limit - p * p) // p + 1)
    return is_prime


def solve() -> None:
    is_prime = sieve(LIMIT)

    # 偶数只能拆成"奇+奇"（2+偶数必非素数），从小到大试奇数，
    # 第一个让两数都是素数的 p 就是题面要求的"最小的第一加数"。
    out: list[str] = []
    for n in range(6, LIMIT + 1, 2):
        p = next(p for p in range(3, n, 2) if is_prime[p] and is_prime[n - p])
        out.append(f"{n}={p}+{n - p}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
41
42
43
44/**
 * 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-10-05 03:51
 * update_at: 2026-10-05 03:51
 */
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXN = 105;

bool is_prime[MAXN]; // is_prime[i] = true 表示 i 是素数

// 埃氏筛，标记 [2, MAXN-1] 范围内的素数
void sieve() {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAXN; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    sieve();
    // 对 6~100 的每个偶数，升序枚举第一个加数，首个两边皆素数的即为最小拆分
    for (int n = 6; n <= 100; n += 2) {
        for (int p = 3; p <= n / 2; p += 2) {
            int q = n - p;
            if (is_prime[p] && is_prime[q]) {
                printf("%d=%d+%d\n", n, p, q);
                break;
            }
        }
    }
    return 0;
}

目录

题目描述

思路

参考代码