素數判斷算法（IsPrime）的三大細節陷阱與優化

素數判斷算法（IsPrime）的三大細節陷阱與優化

IsPrime 看似簡單，實則暗藏邊界條件錯誤、性能隱患、浮點精度導致邏輯錯誤三大陷阱。本文逐一拆解並給出生產級修正方案。

一、陷阱 1：邊界條件缺失

// 錯誤版本
bool IsPrime(int n) {
    if (n % 2 == 0) return false;  // n=2 會誤判為 false！
    for (int i = 3; i <= sqrt(n); i += 2)
        if (n % i == 0) return false;
    return true;  // n=1 會誤判為 true！
}

修正：顯式處理 n ≤ 3。

if (n <= 1) return false;
if (n <= 3) return true;  // 2, 3 是素數
if (n % 2 == 0 || n % 3 == 0) return false;

二、陷阱 2：循環條件重複計算 sqrt

// 低效：每次循環調用 sqrt()
for (int i = 3; i <= sqrt(n); i += 2) ...

優化：循環前預計算，或用整數乘法避免浮點。

// 方案 A：預計算
int limit = (int)sqrt(n);
for (int i = 3; i <= limit; i += 2) ...

// 方案 B：整數乘法（無浮點、無函數調用開銷）
for (int i = 3; i * i <= n; i += 2) ...  // 注意 i*i 可能溢出，n ≤ INT_MAX 時 i ≤ 46340 安全

三、陷阱 3：浮點精度導致邊界判斷錯誤

核心問題：sqrt(49) 可能返回 6.999999999 而非 7.0。若 limit = (int)sqrt(n) 截斷為 6，循環 i <= 6 將漏檢 i=7，導致 49 被誤判為素數！

鐵律修正：向上取整冗餘 1，多檢查一次無傷大雅，少檢查致命。

int limit = (int)sqrt(n) + 1;  // 關鍵 +1
for (int i = 3; i <= limit; i += 2) ...

四、生產級完整實現（6k±1 優化）

bool IsPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;           // 2, 3
    if (n % 2 == 0 || n % 3 == 0) return false;  // 排除 2/3 的倍數
    
    // 所有大於 3 的素數形式為 6k ± 1
    // i 從 5 開始，步長交替 2, 4 (即 5, 7, 11, 13, 17, 19...)
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

五、複雜度與性能對比

六、避坑清單

1. 輸入 int 範圍內，i * i <= n 不溢出（i ≤ 46340）。
2. 嚴禁 i <= sqrt(n) 寫在循環條件中。
3. 邊界 n=0,1,2,3,4,9,25,49 必須測試通過。
4. 大數（> 2^32）必須用 uint64_t + Miller-Rabin。

素數判斷是數論基礎，也是面試、競賽、加密庫的高頻模塊。吃透這三個陷阱，你的 IsPrime 就經得起生產環境考驗。