埃拉托斯特尼篩法

什麼是埃拉托斯特尼篩法？

埃拉托斯特尼篩法是一種用來生成質數的篩法，得名於古希臘數學家 埃拉托斯特尼。
— 維基百科

簡單說：一個古老的 質數篩選演算法，用來找出某個範圍內所有的質數。

質數的定義

質數是指在大於 1 的自然數中，除了 1 和該數自身外，無法被其他自然數整除的數。
— 維基百科

為什麼需要埃篩？

直覺上，判斷 n 是否為質數可以這樣寫：

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2 ; i * i <= n ; ++i){
        if(n % i == 0)
            return false;
    }
    return true;
}

以 1 ~ 30 為例

小練習：標記 1 ~ 60 的質數

為什麼只篩到 \(\sqrt{n}\)？

目標

對於範圍 \([2, n]\) 內的每一個合數 \(c\)，它必定會被某個 \(\leq \sqrt{n}\) 的質數篩掉。

前置知識

• 質數：只能被 1 和自身整除的整數（\(\geq 2\)）
• 合數：除了 1 和自身之外，還有其他因數（\(\geq 2\)）
• 算術基本定理：任何大於 1 的整數都可以唯一分解成質因數乘積
  • 例：\(12 = 2^2 \times 3\)

核心引理

若 \(c\) 是合數，則 \(c\) 的最小質因數 \(p\) 滿足 \(p \leq \sqrt{c}\)

證明（反證法）：假設合數 \(c\) 的所有質因數都 \(> \sqrt{c}\)，那麼至少有兩個質因數 \(r, k\)：

主定理

篩法只需對 \([2, \sqrt{n}]\) 內的質數執行篩除，即可找出 \([2, n]\) 內所有質數。

證明：取 \([2, n]\) 內任意合數 \(c\)

埃篩程式模板

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e7 + 5;
bool is_composite[MAXN]; // true = 合數，false = 質數
vector<int> primes;

void sieve(int n) {
    is_composite[0] = is_composite[1] = true;
    for (int i = 2; i * i <= n; ++i) {
        if (!is_composite[i]) {
            // 從 i*i 開始（更小的倍數已被更小質數標記）
            for (int j = i * i; j <= n; j += i)
                is_composite[j] = true;
        }
    }
    for (int i = 2; i <= n; ++i)
        if (!is_composite[i])
            primes.push_back(i);
}

埃篩的問題

埃篩的核心缺陷：合數會被重複標記

以 n = 12 為例

primes = []

i = 2：未被標記 → primes = [2]
  j=2: 標記 2×2=4,  2 % 2 == 0 → break

i = 3：未被標記 → primes = [2, 3]
  j=2: 標記 3×2=6,  3 % 2 != 0 → 繼續
  j=3: 標記 3×3=9,  3 % 3 == 0 → break

i = 4：已被標記 → 不加入 primes
  j=2: 標記 4×2=8,  4 % 2 == 0 → break   ← 非質數也要跑！

i = 5：未被標記 → primes = [2, 3, 5]
  j=2: 標記 5×2=10, 5 % 2 != 0 → 繼續
  j=3: 標記 5×3=15, 5 % 3 != 0 → 繼續
  j=5: 標記 5×5=25, 5 % 5 == 0 → break

i = 6：已被標記 → 不加入 primes
  j=2: 標記 6×2=12, 6 % 2 == 0 → break

為什麼 i % prime == 0 要 break？

防止重複標記

假設 i = 6，若不 break，想標記 6 × 3 = 18：

推導

當 i % prime == 0 時，設 \(i = prime \times k\)，下一個想標記的合數：

因為質數遞增，\(prime < next_{prime}\)，所以 \(prime\) 才是 \(r\) 真正的最小質因數。 \(r\) 應在未來 \(i' = k \times next_{prime}\) 時被篩掉 → 現在必須 break。

為什麼每個合數恰好被篩一次？

每個合數 \(c\) 都有唯一的最小質因數 \(p\)，可以寫成：

線篩程式碼

const int MAXN = 1e7 + 5;
bool is_composite[MAXN];
vector<int> primes;

void linear_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i])
            primes.push_back(i);     // i 是質數，加入清單

        for (int p : primes) {
            if ((long long)i * p > n) break;  // 超出範圍
            is_composite[i * p] = true;        // 用最小質因數標記

            if (i % p == 0) break;  // ← 核心：確保只篩一次
        }
    }
}

番外：莫比烏斯函數篩

下圖是我看到莫比烏斯函數時的表情：

圖片來源：《蒼之彼方的四重奏》

這也是一個從埃篩延伸出來的東西，但應該用不到，所以只是記錄一下有這個東西。

絕對不是因為我看它有點複雜，不想研究

總結