C# 質數判斷演算法：試除法優化與邊界處理

質數定義：大於 1 的自然數，除 1 與自身外無其他因數。判斷邏輯：檢查 2 到 √n 之間是否有因數，有則為合數，否則為質數。

標準實作

public static bool IsPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;     // 2, 3 是質數
    if (n % 2 == 0) return false; // 排除偶數
    
    int limit = (int)Math.Sqrt(n);
    for (int i = 3; i <= limit; i += 2) { // 只檢查奇數
        if (n % i == 0) return false;
    }
    return true;
}

進階優化：6k ± 1 模式

大於 3 的質數皆為 6k±1 形式：

public static bool IsPrimeOptimized(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;
}

大數質數測試：Miller-Rabin

32 位整數試除法足夠，64 位或大整數建議用機率性測試：

using System.Numerics;

public static bool IsProbablePrime(BigInteger n, int certainty = 10) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    
    // 寫入 n-1 = d * 2^s
    BigInteger d = n - 1;
    int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    
    Random rng = new Random();
    for (int i = 0; i < certainty; i++) {
        BigInteger a = 2 + BigInteger.Abs(new BigInteger(n.ToByteArray())) % (n - 4);
        BigInteger x = BigInteger.ModPow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = BigInteger.ModPow(x, 2, n);
            if (x == n - 1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}

應用範例

Console.WriteLine(IsPrime(2));    // True
Console.WriteLine(IsPrime(17));   // True
Console.WriteLine(IsPrime(100));  // False
Console.WriteLine(IsPrime(9973)); // True (最大四位質數)

常見錯誤提醒

• 原始碼迴圈條件 i > 2 應為 i <= limit
• 未處理 n < 2 的情況
• 未排除偶數導致效率低落
• √n 計算應在迴圈外完成