什么是线性筛

线性筛是一种在 $O(N)$ 时间复杂度内，筛出 $1$ 到 $N$ 中所有质数的算法。它同时也是预处理最小质因子、欧拉函数、约数个数等数论函数的强有力框架。

相比朴素的埃氏筛（埃拉托斯特尼筛法）$O(N\log \log N)$ 的复杂度，线性筛将复杂度压到了真正的线性，代价是代码稍复杂一些，但换来的能力远超单纯的质数筛。

---

埃氏筛的问题

埃氏筛的思想很简单：从小到大遍历，遇到一个质数，就把它的所有倍数标记为合数。

for (int i = 2; i <= n; ++i) {
    if (!is_comp[i]) {
        primes.push_back(i);
        for (int j = i * 2; j <= n; j += i)
            is_comp[j] = true;
    }
}

问题在于，一个合数可能被多个质数重复标记。例如 $12$，会被质数 $2$ 标记一次，又会被质数 $3$ 再标记一次。这种重复操作使得复杂度无法达到线性。

---

线性筛的核心思想

线性筛的目标是：每个合数，只被它的最小质因子筛掉一次。

设合数 $x$ 的最小质因子为 $p$，则 $x=i\times p$。我们希望在枚举 $i$ 时，用质数 $p$ 恰好筛掉 $x$，此后不再用其他质数去碰它。

这就需要一个关键判断：当 $p$ 能整除 $i$ 时，立即停止用更大的质数去筛 $i\times p^{\prime }$，因为这些合数的最小质因子已经不是 $p^{\prime }$，而是 $p$ 了。

---

代码实现与逐行解释

const int MAXN = 1e6 + 5;
int primes[MAXN], cnt;      // 收集质数
bool is_comp[MAXN];         // 是否为合数
int minp[MAXN];             // 最小质因子

void linear_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        // 如果 i 还没有被标记为合数，它就是质数
        if (!is_comp[i]) {
            primes[cnt++] = i;
            minp[i] = i;          // 质数的最小质因子是它自己
        }

        // 用已有的质数去筛合数
        for (int j = 0; j < cnt && i * primes[j] <= n; ++j) {
            int p = primes[j];
            is_comp[i * p] = true;    // i * p 一定是合数
            minp[i * p] = p;          // p 是 i*p 的最小质因子

            if (i % p == 0) break;    // 关键：一旦 p | i，立刻停止
        }
    }
}

if (i % p == 0) break; 为什么关键？

我们手动模拟 $n=6$ 的过程，聚焦这行代码：

• i = 2：质数，primes=[2]。内循环 p=2，筛掉 $4$。i % 2 == 0，break。
• i = 3：质数，primes=[2,3]。内循环 p=2，筛掉 $6$；3%2 != 0，继续；p=3，筛掉 $9$；break。
• i = 4：合数，minp[4]=2。内循环 p=2，筛掉 $8$；4%2==0，break。注意：4 不会和 p=3 相乘，因此 $12$ 不会在这里被筛。
• i = 5：质数，筛掉 $10,15$。
• i = 6：合数，minp[6]=2。内循环 p=2，筛掉 $12$；6%2==0，break。

可以看到，$12$ 被 i=6, p=2 筛掉，而不是被 i=4, p=3 筛掉。这正是因为我们每次都在 i % p == 0 时 break，保证了筛掉每个合数所用的质数，恰好是该合数的最小质因子。

推广到一般情况：对于当前 $i$，设其最小质因子为 $p_0$。当我们枚举质数 $p$ 去乘 $i$ 时：

• 若 $p<p_0$，则 $p$ 是 $i\times p$ 的最小质因子，合理筛掉。
• 若 $p=p_0$，即 i % p == 0，$p$ 恰好是 $i\times p$ 的最小质因子，筛掉后应立即停止。因为下一个更大的质数 $p^{\prime }$ 乘 $i$ 所得的 $i\times p^{\prime }$，它的最小质因子是 $p_0$ 而不是 $p^{\prime }$，应该留给后续更大的 $i^{\prime }$ 用 $p_0$ 去筛。

这样，每个合数都只会进入内循环一次，复杂度严格 $O(N)$。

---

线性筛的扩展能力

线性筛的威力远不止找出质数。在筛的过程中，我们可以顺便求出最小质因子、欧拉函数、约数个数等信息，因为它们都满足积性函数的递推性质。

1. 最小质因子

上文的 minp 数组已经给出。minp[i] 记录了 $i$ 的最小质因子。这使得后续单个数质因数分解的复杂度降为 $O(\log N)$：

void factorize(int x) {
    while (x > 1) {
        int p = minp[x];
        int cnt = 0;
        while (x % p == 0) x /= p, cnt++;
        // 输出或存储 (p, cnt)
    }
}

2. 欧拉函数 $\phi (n)$

欧拉函数 $\phi (n)$ 表示 $1$ 到 $n$ 中与 $n$ 互质的数的个数。它满足：

• $\phi (p)=p-1$（$p$ 是质数）
• 若 $p\mid i$，则 $\phi (i\times p)=\phi (i)\times p$
• 若 $p\nmid i$，则 $\phi (i\times p)=\phi (i)\times (p-1)$

我们可以把它整合到线性筛中：

int phi[MAXN];

void sieve_with_phi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!is_comp[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; ++j) {
            int p = primes[j];
            is_comp[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }
}

3. 约数个数

设 $d(n)$ 为 $n$ 的约数个数，$a(n)$ 为 $n$ 的最小质因子的指数。在线性筛中同样可以维护：

• 若 $n$ 为质数：$d(n)=2$，$a(n)=1$。
• 若 $p\nmid i$，则 $d(i\times p)=d(i)\times 2$，$a(i\times p)=1$。
• 若 $p\mid i$，则 $d(i\times p)=d(i)/(a(i)+1)\times (a(i)+2)$，$a(i\times p)=a(i)+1$。

代码类似，不再赘述。

---

线性筛 vs 埃氏筛

	埃氏筛	线性筛
时间复杂度	$O(N\log \log N)$	$O(N)$
空间复杂度	$O(N)$	$O(N)$
是否重复标记合数	是	否
能否同时求最小质因子	需要额外处理	可以直接整合
能否递推欧拉函数等	不方便	非常方便
代码复杂度	简单	略复杂

在 $N\le 10^7$ 时，埃氏筛的实际速度与线性筛相差不大。但当需要维护最小质因子、欧拉函数等附加信息时，线性筛是首选框架。

---

总结

线性筛通过“每个合数只被最小质因子筛掉一次”的核心机制，将筛法复杂度压到 $O(N)$，并提供了一个可以嵌入多种积性函数递推的框架。理解 if(i % p == 0) break; 这句话，就理解了线性筛的全部精髓。

对于算法竞赛，线性筛是处理 $10^7$ 范围内数论预处理的标准工具，也是后续质因数分解、互质计数、狄利克雷卷积等问题的基础。