「一本通 6.2 练习 3」Goldbach's Conjecture

题目描述

哥德巴赫猜想：任何大于 $4$ 的偶数都能拆成两个奇素数之和。多组询问，每组给出一个 $n$ ，以 $0$ 结束；对每个 $n$ 输出使 $b-a$ 最大的一组分解 $n = a + b$ （ $a,b$ 为奇素数），无解则输出 Goldbach's conjecture is wrong.。数据范围 $6 \le n \le 10^6$ 。样例输入为 8、20、42 各一行并以 0 结束，输出为 8 = 3 + 5、20 = 3 + 17、42 = 5 + 37。

思路

因为 $b - a = n - 2a$ 随 $a$ 增大而减小，所以取使 $n-a$ 为素数的最小奇素数 $a$ 即为答案。先用欧拉筛在 $10^6$ 内打出素数表与判定表，每次询问从最小的奇素数开始枚举， $O(1)$ 判断 $n-a$ 是否素数，找到即输出。

参考代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/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-30 22:32
# update_at: 2026-09-30 22:32

import sys

MAX_V = 1_000_000


def build_sieve(limit: int) -> tuple[bytearray, list[int]]:
    """欧拉筛预处理素数表与质数判定表。"""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    primes: list[int] = []
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > limit:
                break
            is_prime[i * p] = 0
            if i % p == 0:
                break
    return is_prime, primes


def find_goldbach_pair(n: int, primes: list[int], is_prime: bytearray) -> tuple[int, int] | None:
    """寻找使得 n = a + b 且 b - a 最大的奇素数对 (a, b)。"""
    for p in primes:
        if p > n // 2:
            break
        if p == 2:
            continue
        q = n - p
        if is_prime[q]:
            return p, q
    return None


def solve() -> None:
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    is_prime, primes = build_sieve(MAX_V)
    out: list[str] = []
    for token in input_data:
        n = int(token)
        if n == 0:
            break
        pair = find_goldbach_pair(n, primes, is_prime)
        if pair:
            a, b = pair
            out.append(f"{n} = {a} + {b}")
        else:
            out.append("Goldbach's conjecture is wrong.")
    sys.stdout.write("\n".join(out) + "\n")


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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * 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-06 01:18
 * update_at: 2026-10-06 01:18
 */
// roj 1622 Goldbach's Conjecture：欧拉筛预处理素数表，逐组贪心取最小奇素数 a。
#include <iostream>
#include <vector>

typedef long long ll;

const int MAXN = 1000000; // 题面保证 6 <= n <= 10^6

bool is_prime[MAXN + 1]; // is_prime[x] 表示 x 是否为素数
std::vector<int> primes;  // 按升序保存 [2, MAXN] 内的所有素数

// 欧拉筛：O(MAXN) 预处理素数表与素数判定表。
void build_sieve() {
    for (int i = 0; i <= MAXN; i++) {
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= MAXN; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < (int)primes.size(); j++) {
            ll product = (ll)i * primes[j];
            if (product > MAXN) {
                break;
            }
            is_prime[product] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    build_sieve();
    ll n;
    while (std::cin >> n) {
        if (n == 0) {
            break;
        }
        // b - a = n - 2a 随 a 增大而减小，故取最小的奇素数 a 即为最优解。
        bool found = false;
        for (int i = 0; i < (int)primes.size(); i++) {
            ll a = primes[i];
            if (a > n / 2) {
                break;
            }
            if (a == 2) {
                continue; // 只取奇素数，2 留给其他分解
            }
            ll b = n - a;
            if (is_prime[b]) {
                std::cout << n << " = " << a << " + " << b << "\n";
                found = true;
                break;
            }
        }
        if (!found) {
            std::cout << "Goldbach's conjecture is wrong.\n";
        }
    }
    return 0;
}

「一本通 6.2 练习 3」Goldbach's Conjecture

目录

题目描述

思路

参考代码