篩選素數算法總結：從基礎埃氏篩到線性篩（最小質因子法）完整演進

篩選素數算法總結：從基礎埃氏篩到線性篩（最小質因子法）完整演進

本文對比三種篩素數方法，從簡單倍數劃除到線性時間複雜度的最小質因子篩，含代碼、原理與 1 億數據實測。

方法一：基礎埃氏篩（倍數劃除）

從 2 開始，將每個素數的所有倍數標記為合數。

void sieve_basic(int N) {
    vector flag(N, false);
    for (int i=2; i
缺點：合數被多次標記（如 6 被 2 和 3 各標記一次），時間複雜度 O(N log log N) 但常數較大。

方法二：改進版（利用素數表乘積）
每個合數 x = i * p[j]，其中 p[j] 為素數表中素數。

仍有重複：12 = 6×2 = 4×3 會被標記兩次。
void sieve_v2(int N) {
    vector flag(N, false);
    for (int i=2; i

方法三：線性篩（最小質因子唯一標記）★
核心規則：每個合數 僅由其最小質因子 篩除一次。

若 i % primes[j] == 0，說明 primes[j] 是 i 的最小質因子，i * primes[j] 的最小質因子也是 primes[j]，後續更大的質因子不應再標記此數 → break。

否則 primes[j] 不是 i 的因子，繼續嘗試下一個質因子。
void sieve_linear(int N) {
    vector flag(N, false);
    for (int i=2; i

複雜度對比實測（N = 100,000,000）

算法
耗時 (ms)
時間複雜度
基礎埃氏篩
~4,500
O(N log log N)
改進版 v2
~1,800
O(N log N) 但常數較小
線性篩 (O(N))
~600
O(N)

線性篩速度最快且理論優雅，是競程首選。

關鍵點總結

線性篩核心：if (i % p[j] == 0) break; 保證 O(N)。
適用於求 μ(n)、φ(n) 等數論函數（同步計算）。
記憶體：bool flag[N] + int primes[N/3]，N=1e8 約 100MB+130MB，建議用 bitset 或動態位圖壓縮。