C 語言 sqrt() 與強制類型轉換：素數判斷優化的數學原理

代碼片段解析

m <= (int)sqrt(i)

逐層拆解

1. sqrt(i)：計算 i 的平方根，返回 double 類型
   • sqrt(4) = 2.0, sqrt(9) = 3.0
   • sqrt(5) ≈ 2.236, sqrt(10) ≈ 3.162
2. (int)sqrt(i)：強制類型轉換，截斷小數部分 (向零取整)
   • (int)2.236 → 2
   • (int)3.162 → 3
3. m <= ...：循環條件，m 從 2 遞增到 √i 的整數部分

算法優化原理

判斷素數只需檢查到 √n 即可

• 若 n = a × b，則 a ≤ √n 或 b ≤ √n (至少一個因子 ≤ √n)
• 若 2 到 √n 間無因子，則 n 無因子，為素數
• 將循環次數從 O(n) 降為 O(√n)

完整素數判斷函數

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    int limit = (int)sqrt(n);  // 計算一次，避免循環中重複調用
    for (int i = 3; i <= limit; i += 2) {  // 只檢查奇數
        if (n % i == 0) return false;
    }
    return true;
}

進階優化技巧

1. 預計算 limit：避免每次循環調用 sqrt()
2. i += 2：排除偶數，減少一半迭代
3. 6k±1 優化：素數分布在 6k±1 形式，進一步減少 2/3 迭代
4. 查表法：小範圍用埃拉托斯特尼篩法預計算

常見誤區

誤區	正確理解
(int)sqrt(i) 是四捨五入	是截斷/向零取整，2.9 → 2
sqrt 需要 #include <math.h>	C++ 需 ，C 需 並鏈接 -lm
float 精度足夠	大數建議用 double，避免精度損失導致邊界錯誤

總結

(int)sqrt(i) 將浮點平方根截斷為整數，作為循環上界，實現素數判斷從 O(n) 到 O(√n) 的數學優化。這是利用數學性質減少計算量的經典案例。