歌德巴赫猜想驗證：偶數分解為兩素數之和 (C語言實現)

題目要求

輸入 x (≤2000)，若非 ≥6 偶數輸出 `Error!`。否則輸出所有 `x = y + z` (y≤z, y,z 為素數)，按 y 升序。

算法

1. 篩法預計算 2000 以內素數表 `isPrime[]`。
2. 遍歷 `y` 從 2 到 `x/2`，若 `isPrime[y] && isPrime[x-y]` 輸出。

代碼實現

#include 
#include 

#define MAX 2000
bool isPrime[MAX+1];

void sieve() {
    for (int i=2; i<=MAX; i++) isPrime[i] = true;
    for (int i=2; i*i<=MAX; i++)
        if (isPrime[i])
            for (int j=i*i; j<=MAX; j+=i) isPrime[j] = false;
}

int main() {
    sieve();
    int x; scanf("%d", &x);
    if (x < 6 || x % 2 != 0) {
        printf("Error!\n");
        return 0;
    }
    for (int y=2; y<=x/2; y++) {
        if (isPrime[y] && isPrime[x-y])
            printf("%d=%d+%d\n", x, y, x-y);
    }
    return 0;
}

樣例

• 輸入 `10` → `10=3+7`, `10=5+5`
• 輸入 `100` → 6 行分解

參考

xzt6 博客詳解