素數判斷算法優化：從暴力枚舉到乘法替代開根號

素數判斷五種實現的效率演進

素數定義：大於 1 的自然數，除 1 和自身外無其他因數。本文展示從 O(n) 到 O(√n) 再到常數優化的五種 C 語言實現，附複雜度分析。

方法一：暴力遍歷 O(n)

int is_prime_naive(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i < n; ++i)
        if (n % i == 0) return 0;
    return 1;
}

最多 n-2 次循環。n=10^9 時不可接受。

方法二：試除至 √n O(√n)

int is_prime_sqrt(int n) {
    if (n <= 1) return 0;
    int limit = (int)sqrt((double)n);
    for (int i = 2; i <= limit; ++i)
        if (n % i == 0) return 0;
    return 1;
}

數學依據：若 n = a*b，則 a ≤ √n 或 b ≤ √n。循環次數降至 ~31623 (n=10^9)。

方法三：避免重複計算 sqrt O(√n) 低常數

int is_prime_sqrt_once(int n) {
    if (n <= 1) return 0;
    int limit = (int)sqrt((double)n);
    for (int i = 2; i <= limit; ++i)
        if (n % i == 0) return 0;
    return 1;
}

將 sqrt 提到循環外。sqrt 屬較慢的浮點運算，省去每輪調用開銷。

方法四：跳過偶數及 3、5 的倍數 O(√n) 更低常數

int is_prime_skip(int n) {
    if (n <= 1) return 0;
    if (n == 2 || n == 3 || n == 5) return 1;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return 0;
    
    int limit = (int)sqrt((double)n);
    for (int i = 7; i <= limit; i += 2) // 只遍歷奇數
        if (n % i == 0) return 0;
    return 1;
}

排除 2/3/5 的倍數 (佔自然數 ~73%)，步長 2 跳過偶數。實測速度顯著提升。

方法五：乘法替代開根號 O(√n) 無浮點

int is_prime_mul(int n) {
    if (n <= 1) return 0;
    if (n == 2 || n == 3 || n == 5) return 1;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return 0;
    
    for (int i = 7; i * i <= n; i += 2) // i*i <= n 等價 i <= sqrt(n)
        if (n % i == 0) return 0;
    return 1;
}

關鍵優化：i * i <= n 完全用整數乘法替代 sqrt。現代 CPU 整數乘法極快 (1-3 周期)，避免了浮點轉換與庫函數調用開銷，且無精度損失風險。

性能對比 (n = 10^9+7, 10^7 次調用測試)

更高階算法預覽

• Miller-Rabin 素性測試：概率算法，O(k log³ n)，適用 64 位大整數 (k=12 組基底可確定性判斷 2^64 內)。
• 埃拉托斯特尼篩法：批量生成 N 內所有質數，O(N log log N)，單次查詢 O(1)。
• 線性篩 (歐拉篩)：O(N) 篩選，同時得到最小質因子分解。

工程建議

1. 單次判斷 32 位整數：方法五 簡潔高效首選。
2. 批量判斷/生成質數表：線性篩。
3. 64 位大整數：確定性 Miller-Rabin。
4. 嵌入式無 FPU：方法五 避免浮點庫依賴。