為什麼判斷素數只需檢查到 √n？數學原理圖解

直觀疑惑

判斷一個數 n 是否為素數，最直觀的方法是嘗試除以 2 ~ n-1。優化到 n/2 容易理解：因為除數大於一半時商小於 2，不可能整除。但為什麼只需檢查到 √n 就夠了？

核心數學證明

定理：若正整數 n 是合數，則它至少有一個質因數 ≤ √n。

反證法證明

1. 假設 n 是合數，可分解為 n = a × b，其中 1 < a ≤ b < n。
2. 若假設 a > √n 且 b > √n，則 a × b > √n × √n = n，矛盾。
3. 因此 a ≤ √n。即**較小的因子必不超過 √n**。

幾何直觀理解

將因子對 (a, b) 視為矩形的長寬，面積固定為 n。當長寬相等時（即正方形），邊長為 √n。若一邊超過 √n，另一邊必小於 √n。所以只需檢查「短邊」範圍即可。

代碼實現對比

// 低效：檢查到 n-1
for (int i = 2; i < n; i++) ...

// 一般優化：檢查到 n/2
for (int i = 2; i <= n/2; i++) ...

// 最優：檢查到 √n
for (int i = 2; i * i <= n; i++) {  // 避免浮點運算，用 i*i <= n
    if (n % i == 0) return false;
}
return true;

效能差異量級

進階優化技巧

• 跳過偶數：先判斷 2，再從 3 開始步長為 2 迭代。
• 6k±1 優化：大於 3 的質數皆為 6k±1 形式，步長可進一步優化。
• 預計算質數表：埃拉托斯特尼篩法預生成 √n 以內質數，僅用質數試除。

理解 √n 邊界的數學本質，不僅能寫出高效的素數判斷，更能啟發解決其他因數分解類問題的思路。