原理
令當前要處理的數為 $i$，已找到的質數列表為 primes：
- 遍歷 $i$ 從 $2$ 到 $N$。
- 若 $i$ 未被標記為合數，則 $i$ 為質數，加入
primes。 - 用 $i$ 與
primes中的質數 $p$ 相乘（標記合數 $x = i \times p$）：- 標記 $i \times p$ 為合數。
- 關鍵關鍵條件：若 $i \pmod p == 0$，立即中斷（break）內部迴圈。
為什麼
i % p == 0時要 break？
線性篩規定「每個合數只能由它的最小質因數篩掉」，若 $p$ 能整除 $i$，表示 $p$ 是 $i$ 的最小質因數。
如果繼續使用下一個更大的質數 $p_{next}$ 來標記 $i \times p_{next}$，該數的最小質因數其實是 $p$ 而非 $p_{next}$。這樣會導致 $i \times p_{next}$ 未來又被別的更大的 $i$ 和 $p$ 重複篩到，破壞線性時間。
可以想像 $i = a \times p$，有一數 $b = i \times p', p' > p$ 是我們沒有 break 繼續執行篩掉的數，將來等 $i$ 跑到 $i' = a \times p'$，又會遍歷一次 $b = i' \times p = a \times p \times p'$ ，造成多餘的執行結果，break 就是要確保每個數字都會被 $i \times p$ 中最小的 $p$ 篩掉。
舉例來說，$12 = 2 \times 6 = 4 \times 3$ 。如果不執行 break，那麼 $12$ 在 $i = 4$ 的時候會被篩過一次，在 $i = 6$ 時又被篩過一次。如果現在 $i = 4$ 且我們發現 $4 \pmod 2 = 0$ ，表示 $4$ 不是 $12$ 的最小質因數，所以要停下，否則 $12$ 會被篩兩次。
埃氏篩之所以會有 $O(n\log \log n)$ 的時間複雜度，就是因為它會重複篩掉同一個數。
實作
const int MAXN = 1000000;
bool is_composite[MAXN + 1]; // is_composite[x] 為 true 表示 x 是合數
vector<int> primes;
void linear_sieve(int n) {
for (int i = 2; i <= n; ++i) {
if (!is_composite[i]) {
primes.push_back(i);
}
for (int p : primes) {
if (i * p > n) break; // 超出範圍則跳出
is_composite[i * p] = true; // 用最小質因數 p 標記合數
if (i % p == 0) {
break; // 保證每個合數只被最小質因數篩除一次
}
}
}
}
歐拉函數 $\phi (n)$
定義
$\phi(n)$ 表示在 $1 \le k \le n$ 中，與 $n$ 互質的整數個數。
- 質數 $p$ 的歐拉函數：$\phi(p) = p - 1$。
- 通用公式（基於質因數分解 $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$）：
$$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\dots\left(1 - \frac{1}{p_k}\right)$$
性質
當我們用最小質因數 $p$ 去乘上 $i$ 得到新數 $n = i \times p$ 時：
- 若 $i \pmod p \ne 0$（$p$ 不是 $i$ 的因數）：
$i$ 與 $p$ 互質，利用積性函數性質： $$\phi(i \times p) = \phi(i) \times \phi(p) = \phi(i) \times (p - 1)$$ - 若 $i \pmod p == 0$（$p$ 已經是 $i$ 的因數）：
所以 $i \times p$ 與 $i$ 擁有完全一樣的質因數組合，根據公式：
$$\phi(i \times p) = \mathbf{(i \times p)} \times \left(1 - \frac{1}{p}\right) \left(1 - \frac{1}{q_1}\right) \left(1 - \frac{1}{q_2}\right)$$
我們把 $\phi(i \times p)$ 的式子重新整理一下：
$$\phi(i \times p) = p \times \underbrace{\left[ \mathbf{i} \times \left(1 - \frac{1}{p}\right) \left(1 - \frac{1}{q_1}\right) \left(1 - \frac{1}{q_2}\right) \right]}_{\text{這整串就是 } \phi(i)}$$
所以：
$$\phi(i \times p) = p \times \phi(i)$$
莫比烏斯函數 $\mu(n)$
定義
$\mu(n)$ 是莫比烏斯反演（Möbius Inversion）的核心函數，定義如下：
- $\mu(1) = 1$
- 若 $n$ 包含任何次方大於 $1$ 的質因數，則 $\mu(n) = 0$。
- 若 $n$ 為 $k$ 個互不相同的質數之積（$n = p_1 p_2 \dots p_k$），則 $\mu(n) = (-1)^k$。
性質
當我們用最小質因數 $p$ 去乘上 $i$ 得到新數 $n = i \times p$ 時：
- 若 $i \pmod p \ne 0$：
$i \times p$ 比 $i$ 多了一個不同的質因數，質因數個數加 $1$： $$\mu(i \times p) = -\mu(i)$$ - 若 $i \pmod p == 0$：
$i \times p$ 包含了至少兩個 $p$（即含有 $p^2$ 平方因子）： $$\mu(i \times p) = 0$$
實作
const int MAXN = 1000000;
bool is_composite[MAXN + 1];
vector<int> primes;
int lpf[MAXN + 1]; // 紀錄最小質因數
int phi[MAXN + 1]; // 歐拉函數
int mu[MAXN + 1]; // 莫比烏斯函數
void sieve(int n) {
lpf[1] = 1;
phi[1] = 1;
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!is_composite[i]) {
primes.push_back(i);
lpf[i] = i;
phi[i] = i - 1; // 質數 p 的 phi(p) = p - 1
mu[i] = -1; // 質數 p 的 mu(p) = -1
}
for (int p : primes) {
if (i * p > n) break;
is_composite[i * p] = true;
lpf[i * p] = p;
if (i % p == 0) {
// p 是 i 的因數
phi[i * p] = phi[i] * p;
mu[i * p] = 0; // 包含平方因子 p^2
break; // 保證線性複雜度
} else {
// p 與 i 互質
phi[i * p] = phi[i] * (p - 1);
mu[i * p] = -mu[i];
}
}
}
}