C語言求質數/素數完整指南：試除法、埃氏篩、米勒-拉賓、優化技巧與工程級實現

核心定義

質數：大於 1 的自然數，除 1 和自身外無其他正因子。1 不是 質數。

演算法層級對比

1. 單次判斷：優化試除法 (工程首選)

#include 
#include 
#include 

/* 判斷 64 位無符號整數是否為質數 */
bool is_prime_u64(uint64_t n) {
    if (n <= 1) return false;
    if (n <= 3) return true;           // 2, 3
    if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2, 3 的倍數

    /* 6k ± 1 優化：所有質數 > 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;
}

/* 32 位版本 (更快，避免 64 位乘法溢出檢查) */
bool is_prime_u32(uint32_t n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (uint32_t i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

2. 批量生成：線性篩 (歐拉篜) — 獲取最小質因數分解

#include 
#include 
#include 

/* 線性篩：返回 n 以內質數列表，並填充最小質因數數組 lpf (可選) */
uint32_t *linear_sieve(uint32_t n, uint32_t **out_primes, size_t *out_count, uint32_t **out_lpf) {
    uint8_t *is_composite = calloc(n + 1, 1); // 0: prime, 1: composite
    uint32_t *primes = malloc((n / 10) * sizeof(uint32_t)); // 估算質數個數 ~ n/ln n
    size_t p_cnt = 0;
    uint32_t *lpf = out_lpf ? malloc((n + 1) * sizeof(uint32_t)) : NULL;

    for (uint32_t i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes[p_cnt++] = i;
            if (lpf) lpf[i] = i;
        }
        for (size_t j = 0; j < p_cnt; ++j) {
            uint64_t mul = (uint64_t)i * primes[j];
            if (mul > n) break;
            is_composite[mul] = 1;
            if (lpf) lpf[mul] = primes[j];
            if (i % primes[j] == 0) break; // 核心：保證每個合數只被最小質因數篩一次
        }
    }
    free(is_composite);
    primes = realloc(primes, p_cnt * sizeof(uint32_t));
    *out_primes = primes;
    *out_count = p_cnt;
    if (out_lpf) *out_lpf = lpf;
    return primes;
}

3. 大整數 (64位) 確定性米勒-拉賓

#include 
#include 

/* 模乘：避免溢出 (a * b) % mod，使用 __int128 (GCC/Clang) 或加法模擬 */
static inline uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod) {
#if defined(__SIZEOF_INT128__)
    return (unsigned __int128)a * b % mod;
#else
    uint64_t res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
#endif
}

/* 模冪：快速冪取模 */
static uint64_t pow_mod(uint64_t a, uint64_t d, uint64_t mod) {
    uint64_t res = 1;
    while (d) {
        if (d & 1) res = mul_mod(res, a, mod);
        a = mul_mod(a, a, mod);
        d >>= 1;
    }
    return res;
}

/* 米勒-拉賓單輪測試 */
static bool miller_rabin_witness(uint64_t n, uint64_t a, uint64_t d, int 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; // 肯定為合數
}

/* 確定性米勒-拉賓：對 64 位整數，測試基 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 保證正確 */
bool is_prime_miller_rabin_u64(uint64_t n) {
    if (n < 2) return false;
    static const uint32_t small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (size_t i = 0; i < sizeof(small_primes)/sizeof(small_primes[0]); ++i) {
        if (n == small_primes[i]) return true;
        if (n % small_primes[i] == 0) return false;
    }

    uint64_t d = n - 1;
    int s = 0;
    while ((d & 1) == 0) { d >>= 1; ++s; }

    static const uint64_t bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (size_t i = 0; i < sizeof(bases)/sizeof(bases[0]); ++i) {
        if (bases[i] % n == 0) continue;
        if (miller_rabin_witness(n, bases[i], d, s)) return false;
    }
    return true;
}

4. 位元組篩優化：極致空間/時間效率 (n ≤ 10^9)

• 僅存儲奇數：`index = (n - 3) / 2`，空間減半。
• 位元組壓縮：每 bit 代表一個奇數，空間再減 8 倍 (10^9 需 ~60MB)。
• 快取友好分段篩：按 L1/L2 快取大小分塊處理，減少快取未命中。
• 輪因子跳過：跳過 3/5/7 的倍數 (模 30/210/2310)，進一步減少操作數。

工程級選型建議

常見錯誤避坑

• ❌ `for (i=2; i<=n/2; i++)` — 邊界應為 `i*i <= n` 或 `i <= sqrt(n)`。
• ❌ `if (n % i == 0) return false; break;` — `break` 在 `return` 後永不執行 (原始問題代碼錯誤)。
• ❌ 忽略 `n <= 1` 邊界 (1 不是質數)。
• ❌ 用 `int` 存儲大質數導致溢出，用 `` 精確型別。
• ❌ 篩法數組大小棧上分配 (`bool is_prime[10000000]`) 導致棧溢出，用靜態/動態分配 (全域/heap)。

總結

質數判斷與生成是演算法基石。單次判斷用優化試除法 (6k±1) 或確定性米勒-拉賓；批量生成用線性篩 (歐拉篩)；極大規模用分段位元組篩/專業計數算法。工程中優先使用成熟庫，自行實現時嚴守邊界、型別精確、記憶體安全、編譯器優化友好。掌握這些模式，應對面試、競程、工程開發遊刃有餘。