C語言求 100-200 間素數：k=sqrt(m) 優化原理解析

代碼片段

for (m = 101; m <= 200; m++) {
    k = sqrt(m);
    for (i = 2; i <= k; i++)
        if (m % i == 0) break;
    if (i > k) printf("%d ", m);
}

為什麼開平方根？

若一個數 `m` 有因數 `d` 且 `d > sqrt(m)`，則其配對因數 `m/d` 必然 `< sqrt(m)`。因此只需檢查到 `sqrt(m)` 即可覆蓋所有可能因數，減少一半以上循環次數。

舉例

`m = 36`，`sqrt(36) = 6`。只需試除 2~6：
2✓, 3✓, 4✓, 5✗, 6✓ → 發現因數，非素數。
無需試 9, 12, 18，因其配對因數 4, 3, 2 已在 2~6 中檢查過。

進一步優化

• 預先篩選偶數（`m` 從 101 起步，步長 2）。
• 使用埃拉托斯特尼篩法預生成 200 以內素數表，O(1) 判斷。