C語言驗證哥德巴赫猜想：素數判定與偶數拆解完整實現

前言

哥德巴赫猜想：任意大於6的偶數均可表示為兩個素數之和。本文提供基於 int 型別的完整C語言驗證程式，涵蓋素數判定優化、猜想驗證邏輯、使用者互動介面，適合演算法入門練習與教學演示。

一、核心演算法設計

1. 素數判定 IsPrimeNumber()

• 1 和 2 直接視為素數（題目定義）。
• 其餘數 n：只需試除至 √n。若存在除數，則非素數。
• 優化：從 √n 向下遞減試除，發現因子即提前返回。

static bool IsPrimeNumber(int intNum) {
    if (intNum == 1 || intNum == 2) return true;
    int sqr = (int)sqrt((double)intNum);
    for (int i = sqr; i >= 2; i--) {
        if (intNum % i == 0) return false;
    }
    return true;
}

2. 猜想驗證 ISGDBHArith()

• 輸入必須為偶數且 > 6。
• 枚舉 i = 1 .. n/2，檢查 i 與 n-i 是否皆為素數。
• 找到第一組即輸出等式並返回成功（或繼續尋找所有組合）。

static bool ISGDBHArith(int intNum) {
    if (intNum % 2 != 0 || intNum <= 6) return false;
    for (int i = 1; i <= intNum / 2; i++) {
        if (IsPrimeNumber(i) && IsPrimeNumber(intNum - i)) {
            printf("%d = %d + %d\n", intNum, i, intNum - i);
            return true; // 找到一組即可證明該數符合猜想
        }
    }
    return false;
}

二、完整可執行程式

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

// ... 上述兩個函數 ...

int main() {
    int a = 0;
    printf("請輸入一個大於6的偶數：\n");
    if (scanf("%d", &a) != 1) return 1; // 輸入失敗保護

    if (ISGDBHArith(a)) {
        printf("%d 能寫成兩個素數之和，符合哥德巴赫猜想。\n", a);
    } else {
        printf("%d 不符合條件（非大於6的偶數）或未找到素數對。\n", a);
    }
    return 0;
}

注意：原碼使用 scanf_s（MSVC專用）與 getchar() 留存控制台，上述改為標準 scanf，跨平台更佳。

三、執行範例

請輸入一個大於6的偶數：
20
20 = 3 + 17
20 = 7 + 13
20 能寫成兩個素數之和，符合哥德巴赫猜想。

四、效能與型別限制討論

• int 型別通常為32位有號（範圍 ±21億），驗證範圍限於 2 ~ 2,147,483,646。
• 試除法複雜度 O(√n)，單次驗證 n=2e9 約需 4.6 萬次模運算，現代CPU毫秒級完成。
• 擴展至 64 位整數（long long / int64_t）需改用 Miller-Rabin 概率素性測試，試除法不再適用。
• 批量驗證區間內所有偶數時，建議預先用埃拉托斯特尼篩法生成素數表，查表 O(1) 替代試除。

五、總結

這個小程式雖簡單，卻串聯了數學定義轉化為邏輯、邊界條件處理、函數分解與復用、標準庫使用（math.h, stdbool.h）、跨平台輸入輸出等核心編程技能，是演算法入門的優秀練習題。