為什麼判斷素數只需循環到 Math.sqrt(n)？

代碼片段

for (int i = 101; i < 200; i++) {
    boolean isPrime = true;
    for (int j = 2; j <= Math.sqrt(i); j++) {  // 關鍵行
        if (i % j == 0) { isPrime = false; break; }
    }
    if (isPrime) { System.out.print(i + " "); count++; }
}

數學原理

若 n = a × b，則 a ≤ √n 或 b ≤ √n（否則乘積 > n）。

因此至少有一個因子 ≤ √n，只需檢查到 √n 即可確定是否為合數。

效能提升

• n = 100：暴力法 98 次模運算 → √n 法 9 次，提升 10 倍+。
• 隨 n 增大，優勢呈指數級擴大。

完整輸出（101-200 素數）

101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
共 21 個素數

結論：Math.sqrt(i) 將時間複雜度從 O(n) 降為 O(√n)，是素數判斷的標準優化手段。