ZeroJudge 解題筆記：c050. 00453 - Goldbach's Conjecture

作者：王一哲
日期：2026年2月10日


ZeroJudge 題目連結：c050. 00453 - Goldbach's Conjecture

解題想法

先建立 1000000 以內的質數表 primes，但是不包含 2，因為題目要測試的數字大於 4。如果要測試的數字為 $n$，先用二分搜尋法從表格中找到最接近且大於等於 $n$ 的質數索引值 $idx$，接下來從 3 開始往上找到 $primes[idx]$ 為止，最早找到的解就是差值最大的解。

Python 程式碼

使用時間約為 1 s，記憶體約為 25.5 MB，通過測試。

import sys, bisect

### 建立 1 ~ 1000000 的質數表，不包含 2 ###
maxn = 1000000
sieve = [True]*(maxn+1)
sieve[0] = sieve[1] = False
for i in range(0, maxn+1, 2): sieve[i] = False
for i in range(3, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, maxn+1, i):
            sieve[j] = False
primes = [i for i in range(maxn+1) if sieve[i]]

### 主要的解題過程 ###
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    n = int(data[ptr])
    ptr += 1
    if n == 0: break
    idx = bisect.bisect_left(primes, n)
    a, b = 0, 0
    for x in primes[:idx+1]:  # 從 3 開始往上找，最早找到的解就是差值最大的解
        y = n-x
        idy = bisect.bisect_left(primes, y)
        if primes[idy] == y:
            a, b = x, y
            break
    if a == 0 and b == 0:
        reesult.append("Goldbach's conjecture is wrong.\n")
    else:
        result.append(f"{n:d} = {a:d} + {b:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 15 ms，記憶體約為 1.2 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    /* 建立 1 ~ 1000000 的質數表，不包含 2 */
    const int maxn = 1000000;
    vector<bool> sieve (maxn+1, true);
    for(int i=2; i<=maxn; i+=2) sieve[i] = false;
    sieve[0] = false;
    sieve[1] = false;
    for(int i=3; i<=1000; i++) {
        if (sieve[i]) {
            for(int j=i*i; j<=maxn; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=0; i<=maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    /* 主要的解題過程 */
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        int idx = lower_bound(primes.begin(), primes.end(), n) - primes.begin();
        int a = 0, b = 0;
        for(int i=0; i<=idx; i++) {  // 從 3 開始往上找，最早找到的解就是差值最大的解
            int x = primes[i];
            int y = n-x;
            int idy = lower_bound(primes.begin(), primes.end(), y) - primes.begin();
            if (primes[idy] == y) {
                a = x; b = y;
                break;
            }
        }
        if (a == 0 && b == 0) puts("Goldbach's conjecture is wrong.");
        else printf("%d = %d + %d\n", n, a, b);
    }
    return 0;
}