C語言判斷素數演算法：為什麼只需檢查到 sqrt(i) 即可？

為什麼 j <= sqrt((double)i) 就足夠？

假設 i = a × b，其中 a ≤ b，那麼 a ≤ √i ≤ b。若 i 有因數，必定存在一個因數 ≤ √i。因此，若在 2 到 √i 之間找不到任何因數，i 必為素數。

程式碼範例解析

for (j = 2; j <= sqrt((double)i); j++) {
    if (i % j == 0) y = 0; // 發現因數，非素數
}

(double) 強制轉型是為了讓 sqrt() 接收浮點數參數，避免整數除法導致精度損失。這裡的 y 作為旗標，初始為 1（假設為素數），一旦發現能整除即設為 0。

效能比較

以判斷 10,000 以內的素數為例：

• j < i：約需 5,000 萬次迴圈
• j <= sqrt(i)：僅需約 60 萬次迴圈

效能提升超過 80 倍，這在大規模素數篩選中極為關鍵。

延伸應用：哥德巴赫猜測驗證

原始程式碼進一步應用此演算法，嘗試將偶數 a 分解為兩個素數之和（i + d = a），同樣利用 sqrt 優化雙重素數檢測。