C# 質數判定演算法實作與優化

質數定義

大於 1 的自然數，僅能被 1 與自身整除。1、2、3 為質數。判定邏輯：以 2 至 √n 為除數試除，任一整除即為合數，否則為質數。

基礎實作

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

namespace ExPrimeNumber
{
    class PrimeNumber
    {
        public bool IsPrime(int n)
        {
            if (n == 1 || n == 2) return true;
            int limit = (int)Math.Sqrt(n);
            for (int i = limit; i >= 2; i--)
            {
                if (n % i == 0) return false;
            }
            return true;
        }

        static void Main(string[] args)
        {
            Console.Write("請輸入一個數：");
            int n = Convert.ToInt32(Console.ReadLine());
            PrimeNumber p = new PrimeNumber();
            bool b = p.IsPrime(n);
            Console.WriteLine("{0} {1}質數", n, b ? "是" : "不是");
        }
    }
}

關鍵優化點

1. 試除上限 √n：若 n = a×b，則 a≤√n 或 b≤√n，僅需檢測至平方根。
2. 遞減迴圈：從 √n 向下檢測，大因數優先發現，合數平均更快判定。
3. 跳過偶數：n>2 且為偶數直接回傳 false；迴圈步進 2（僅檢測奇數）。
4. 6k±1 優化：質數（>3）皆為 6k±1 形式，試除步進 6，每輪檢測 i 與 i+2。

進階演算法（大數適用）

• Miller-Rabin：概率性測試，O(k log³ n)，k 為測試輪數，工程常用（k=10 錯誤率 < 2⁻²⁰）。
• AKS：決定性多項式時間，理論意義大但實務較慢。
• 預篩選：小質數表（<1000）快速排除明顯合數。

應用場景建議