素數高效判定算法完全指南：從試除法到 Miller-Rabin 確定性測試與 C 實現

算法演進全景

工程級確定性 Miller-Rabin (64 位整數)

對於 n < 2^64，測試基集 {2, 3, 5, 7, 11, 13, 17} (或 {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) 即可**確定性**判斷質數，無錯誤概率。

核心組件：模乘 (防溢出) 與模冪

// (a * b) % mod  無溢出 (mod < 2^63)
static inline uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod) {
#if defined(__SIZEOF_INT128__)
    return (__uint128_t)a * b % mod; // GCC/Clang 128 位原生支持
#else
    uint64_t res = 0;
    a %= mod;
    while (b) {
        if (b & 1) { res += a; if (res >= mod) res -= mod; }
        a <<= 1; if (a >= mod) a -= mod;
        b >>= 1;
    }
    return res;
#endif
}

// (base^exp) % mod
static uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t res = 1;
    base %= mod;
    while (exp) {
        if (exp & 1) res = mul_mod(res, base, mod);
        base = mul_mod(base, base, mod);
        exp >>= 1;
    }
    return res;
}

Miller-Rabin 核心邏輯

// n-1 = d * 2^s, d 奇數
static bool miller_rabin_witness(uint64_t a, uint64_t n) {
    if (a % n == 0) return false; // 基數是 n 的倍數，跳過
    uint64_t d = n - 1;
    int s = 0;
    while ((d & 1) == 0) { d >>= 1; s++; }
    uint64_t x = pow_mod(a, d, n);
    if (x == 1 || x == n - 1) return false; // 可能是質數
    for (int r = 1; r < s; ++r) {
        x = mul_mod(x, x, n);
        if (x == n - 1) return false; // 可能是質數
    }
    return true; // 肯定是合數
}

bool is_prime(uint64_t n) {
    if (n < 2) return false;
    // 小質數快速篩除
    static const uint64_t small_primes[] = {2,3,5,7,11,13,17,19,23,29,31,37};
    for (uint64_t p : small_primes) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    // 確定性基集 (n < 2^64)
    static const uint64_t bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (uint64_t a : bases) {
        if (miller_rabin_witness(a, n)) return false; // 合數
    }
    return true; // 質數
}

尋找第 k 個大於 m 的質數

void find_k_primes_after(uint64_t m, int k, uint64_t *out) {
    int found = 0;
    uint64_t x = m + 1;
    if ((x & 1) == 0) x++; // 確保奇數
    while (found < k) {
        if (is_prime(x)) out[found++] = x;
        x += 2; // 只檢查奇數
    }
}

性能基準 (Intel i7-12700K, -O2)

32 位嵌入式平台優化 (無 int128)

// 32 位平台模乘 (mod < 2^31)
static uint32_t mul_mod32(uint32_t a, uint32_t b, uint32_t mod) {
    uint64_t res = (uint64_t)a * b;
    return res % mod; // 64 位中間結果足夠
}
// 基集縮減: n < 2^32 只需 {2, 7, 61} (確定性)
static const uint32_t bases32[] = {2, 7, 61};

對比：試除法優化版 (適用小數/教學)

bool is_prime_trial(uint64_t n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    // 6k ± 1 形式
    for (uint64_t i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

選型決策樹

需要判定單個大數 (n > 10^12)?
  ├─ 是 → Miller-Rabin 確定性版 (64位用7基數)
  └─ 否 → 需要批量查詢小範圍?
         ├─ 是 → 埃氏篩 / 線性篩 預計算
         └─ 否 → 試除法 6k±1 優化版 (代碼最短)

常見錯誤

1. ❌ i * i <= n 溢出 (i 為 64 位) → 用 i <= n / i 或 __int128。
2. ❌ 忽略小質數篩除 → Miller-Rabin 測試大量基數浪費時間。
3. ❌ 32 位平台用 64 位乘法無 __int128 → 必須用俄羅斯農夫乘法或雙精度浮點近似 (需誤差分析)。
4. ❌ 將概率版當確定性用 → 選錯基集導致偽質數通過 (如 3215031751 通過 {2,3,5,7} 但為合數)。

總結

現代工程中，**確定性 Miller-Rabin (7 基數)** 是 64 位整數質數判定的**黃金標準**：理論無誤、實際極快 (百納秒級)、代碼量適中、無依賴。批量小範圍用篩法，單個小數用試除。掌握模乘防溢出、模冪二進制分解、基集選擇、小質數預篩，即可在任何 C/C++ 項目中自信處理質數問題。