C# 實作哥德巴赫猜想驗證：偶數拆解為兩質數之和

哥德巴赫猜想：大於 2 的偶數皆可表示為兩質數之和（強哥德巴赫猜想）。本文實作驗證程式，輸入偶數輸出所有質數對組合。

核心演算法

1. 驗證輸入為大於 2 的偶數
2. 遍歷 2 到 n/2，檢查 i 與 n-i 是否皆為質數
3. 輸出所有符合組合

完整實作

public class GoldbachConjecture {
    public bool IsPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        int limit = (int)Math.Sqrt(n);
        for (int i = 5; i <= limit; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }
    
    public List<Tuple<int, int>> FindPrimePairs(int n) {
        var pairs = new List<Tuple<int, int>>();
        if (n <= 2 || n % 2 != 0) return pairs;
        
        for (int i = 2; i <= n / 2; i++) {
            if (IsPrime(i) && IsPrime(n - i)) {
                pairs.Add(Tuple.Create(i, n - i));
            }
        }
        return pairs;
    }
}

// 使用範例
var gc = new GoldbachConjecture();
var pairs = gc.FindPrimePairs(100);
foreach (var p in pairs) {
    Console.WriteLine($"100 = {p.Item1} + {p.Item2}");
}
// 輸出：
// 100 = 3 + 97
// 100 = 11 + 89
// 100 = 17 + 83
// 100 = 29 + 71
// 100 = 41 + 59
// 100 = 47 + 53

效能優化：質數篩法預計算

public class PrimeSieve {
    private bool[] isPrime;
    
    public PrimeSieve(int maxN) {
        isPrime = new bool[maxN + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= maxN; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxN; j += i)
                    isPrime[j] = false;
            }
        }
    }
    
    public bool IsPrime(int n) => n >= 0 && n < isPrime.Length && isPrime[n];
}

// 驗證 100 萬以內所有偶數
var sieve = new PrimeSieve(1_000_000);
for (int n = 4; n <= 1_000_000; n += 2) {
    bool found = false;
    for (int i = 2; i <= n / 2; i++) {
        if (sieve.IsPrime(i) && sieve.IsPrime(n - i)) { found = true; break; }
    }
    if (!found) Console.WriteLine($"反例：{n}");
}
Console.WriteLine("驗證完成，無反例");

數學背景

• 1742 年克里斯蒂安·哥德巴赫致信尤拉提出
• 陳景潤 1966 年證明「1+2」結果：大於 2 的偶數可寫為兩質數或一質數與一半質數之和
• 截至 2023 年，電腦已驗證至 4×10¹⁸ 無反例