C# 實作歌德巴赫猜想驗證演算法

問題描述

歌德巴赫猜想：任意大於 6 的偶數，皆可表示為兩個質數之和。本文提供 C# 驗證實作，輸入偶數輸出所有質數對組合。

核心演算法

質數判定 IsPrimeNumber

• 1、2 視為質數（依題目定義）。
• 其餘數值：僅需檢測 2 到 sqrt(n) 之間的除數，存在整除則非質數。
• 優化：從 sqrt(n) 遞減檢測，提早發現大因數。

猜想驗證 goldbachConjecture

• 輸入驗證：偶數且 > 6。
• 遍歷 i = 1 ~ n/2，同步檢測 i 與 n-i 是否皆為質數。
• 滿足條件輸出組合 n = i + (n-i)，標記驗證通過。

完整程式碼

using System;
using System.Collections.Generic;
using System.Text;

namespace ExGoldbachConjecture
{
    class GoldbachConjecture
    {
        public bool IsPrimeNumber(int n)
        {
            bool b = true;
            if (n == 1 || n == 2)
                b = true;
            else
            {
                int sqr = Convert.ToInt32(Math.Sqrt(n));
                for (int i = sqr; i >= 2; i--)
                {
                    if (n % i == 0)
                    {
                        b = false;
                    }
                }
            }
            return b;
        }

        public bool goldbachConjecture(int n)
        {
            bool b = false;
            if (n % 2 == 0 && n > 6)
            {
                for (int i = 1; i <= n / 2; i++)
                {
                    bool b1 = IsPrimeNumber(i);
                    bool b2 = IsPrimeNumber(n - i);
                    if (b1 & b2)
                    {
                        Console.WriteLine("{0}={1}+{2}", n, i, n - i);
                        b = true;
                    }
                }
            }
            return b;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("輸入一個大於 6 的偶數");
            int n = Convert.ToInt32(Console.ReadLine());
            GoldbachConjecture g = new GoldbachConjecture();
            bool b = g.goldbachConjecture(n);
            if (b)
                Console.WriteLine("{0} 能寫成兩個質數的和。", n);
            else
                Console.WriteLine("猜想錯誤。");
        }
    }
}

執行範例

輸入一個大於 6 的偶數
20
20=3+17
20=7+13
20 能寫成兩個質數的和。

複雜度與優化方向

• 時間複雜度：O(n√n)，n 為輸入偶數。
• 可引入 埃拉托斯特尼篩法 預計算質數表，將單次判定降為 O(1)，整體降為 O(n)。
• 大數驗證可採用 Miller-Rabin 概率質數測試。