看似正確實則危險：素數判定中 k = sqrt(n) 的浮點數陷阱與整數替代方案

判斷素數的經典代碼：

int k = sqrt(n);
for (int i = 2; i <= k; i++) if (n % i == 0) return false;

乍看合理，實則隱藏**浮點數精度丟失**導致邊界錯誤的風險。本文深入剖析根因，並提供純整數的安全替代實作。

浮點數陷阱詳解

1. sqrt 返回 `double`，隱式轉換為 `int` 截斷小數部。
2. 對於大整數 (如 64 位)，`double` 只有 53 位尾數精度，**無法精確表示所有整數**，`sqrt` 結果可能比真實值略小或略大。
3. 若 `k` 偏小 (如真實 √n = 1000000.0000001 算成 999999)，迴圈漏檢因子 → **假素數**。
4. 若 `k` 偏大，多跑幾次無傷大雅，但效率微降。
5. 編譯器優化可能將 `sqrt` 移出循環，但精度問題依然存在。

經典反例

int n = 2147483647; // 2^31-1，素數
// 若 sqrt 精度不足算出 k = 46339 (實際 √n ≈ 46340.95)
// 迴圈只跑到 46339，漏檢 46340？其實 46340^2 > n，但邊界邏輯已破壞。

純整數安全替代：奇數平方和法

利用數學恆等式：1 + 3 + 5 + ... + (2k-1) = k²。累加奇數直到和 ≥ n，項數即為 ⌈√n⌉。

int isqrt_ceil(int n) {
    int sum = 0, odd = 1, k = 0;
    while (sum < n) { sum += odd; odd += 2; k++; }
    return k; // 返回最小的 k 使得 k*k >= n
}

bool is_prime(int n) {
    if (n <= 3) return n > 1;
    if (n % 2 == 0) return false;
    int k = isqrt_ceil(n);
    for (int i = 3; i <= k; i += 2)
        if (n % i == 0) return false;
    return true;
}

優勢對比

工程建議

• 32 位 `int` 範圍內，`sqrt` 通常安全，但**不建議依賴未定義行為**。
• 64 位 `long long` **必須**用整數方法 (二分/牛頓/庫函數 `isqrt` C23)。
• 嵌入式無 FPU 環境，整數法更無浮點庫依賴。
• 素數測試大數建議用 **Miller-Rabin** (概率) 或 **AKS** (確定性)。

細節決定可靠性。拒絕「似是而非」的 `k = sqrt(n)`，擁抱精確的整數邊界計算，寫出經得起邊界測試的代碼。