C語言判斷素數的核心邏輯：為何只需試除到 √n？

素數判定的數學直覺

判斷一個正整數 n 是否為素數，最直觀的方法是嘗試用 2 到 n-1 的所有整數去除。但這顯然效率極低。數學上有一個關鍵性質：若 n 為合數，則至少存在一個不大於 √n 的質因數。利用這一性質，試除範圍可壓縮至 [2, ⌊√n⌋]，時間複雜度從 O(n) 降為 O(√n)。

為什麼 √n 是分水嶺？

假設 n = a × b（a ≤ b），則 a² ≤ a×b = n，即 a ≤ √n。換句話說，任一合數至少有一個因子 ≤ √n。若在 2~√n 區間找不到任何因數，則 n 必為素數——因為若存在大於 √n 的因子，其配對的另一因子必小於 √n，早已被檢測到。

C語言實作範例

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

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;          // 排除偶數
    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2) {  // 只檢查奇數
        if (n % i == 0) return false;
    }
    return true;
}

進階優化方向

• 6k±1 優化：除 2、3 外，所有質數均形如 6k±1，步長可進一步縮減。
• 預篩小質數：先用小質數表（如 2,3,5,7,11...）快速排除明顯合數。
• Miller-Rabin 素性測試：對大整數（> 2³²）採用概率演算法，極快且可控錯誤率。

總結

「只需試除到 √n」並非經驗法則，而是源於因數成對出現的基本算術性質。掌握這一數學本質，能寫出既正確又高效的素數判定程式，也是演算法優化思維的經典入門案例。