线性筛法：为什么 i % p == 0 时要 break？

· · 算法·理论

前言

网上关于线性筛法的教程并不少。大多数教程都会强调，代码中的

if (i % p == 0) break;

可以保证每个合数只被筛一次。然而在我学习线性筛法时，即使记住了这个结论，也很难真正理解：为什么这样一句判断就能避免重复标记？

后来，我逐渐想清楚了这条语句背后的原理，因此想结合自己的理解，对线性筛法作一次较为完整的说明。本文会将重点放在上述 break 语句上。

一、回顾埃氏筛法

埃拉托斯特尼筛法（以下简称“埃氏筛”）基于一个简单的事实：

一个质数的正整数倍（不包括它本身）一定是合数。

我们可以使用 vis 数组记录一个数是否已经被判定为合数：若 vis[x] = true，则说明 x 是合数。

一种基本实现如下：

vector<bool> vis(n + 1, false);

vis[1] = 1; // 1不为素数

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

假设当前枚举到 i。如果 vis[i] = false，说明不存在小于 i 的质因子能够整除 i，因此 i 本身一定是质数。随后，我们将不超过 n 的、除 i 本身以外的所有 i 的倍数标记为合数。形式化地说，就是标记

j=k\times i,\qquad k\ge 2,\quad j\le n

但是，这种做法可能会多次标记同一个合数。

例如：

210=2\times 3\times 5\times 7

当 i 分别取 2、3、5 和 7 时，210 都可能作为相应质数的倍数被标记。虽然重复标记不会影响结果的正确性，但会产生冗余操作。

二、线性筛法的目标

线性筛法（也称欧拉筛）的核心目标是：

让每个合数只被它的最小质因子标记一次。

例如，6 的最小质因子是 2，因此我们只希望通过

6=2\times 3

将其标记，而不再用质因子 3 重复标记它。

设合数 x 的最小质因子为 p_{\min}，并令

t=\frac{x}{p_{\min}}

那么

x=t\times p_{\min}

线性筛规定：x 只在外层循环枚举到 t、内层循环枚举到 p_{\min} 时被标记。

为了实现这一目标，除了 vis 数组之外，还需要使用 primes 数组，按照从小到大的顺序保存目前已经找到的所有质数。

三、代码模板

vector<bool> vis(n + 1, false);
vector<int> primes;

vis[1] = 1; 

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

    for (int p : primes) {
        if (i * p > n) break; // 处理边界

        vis[i * p] = true;       // 重点 1：标记合数 i * p

        if (i % p == 0) break;   // 重点 2：p 能整除 i 时停止
    }
}

四、vis[i * p] = true 在做什么？

在埃氏筛中，当我们找到一个质数 i 后，会枚举它的各个倍数。

在线性筛中，外层循环的 i 不一定是质数。对于每个 i，我们从小到大枚举 primes 中的质数 p，并尝试标记

i\times p

例如，当 i=3，且 primes = [2, 3] 时，会依次标记

3\times 2=6,\qquad 3\times 3=9

随着外层循环继续向后移动，其他合数也会以类似的形式被标记。不过，内层循环并不会无条件枚举所有已知质数，而是在第一次遇到能够整除 i 的质数时停止。这正是线性筛能够避免重复标记的关键。

五、为什么 i % p == 0 时必须停止？

假设 primes 中的质数依次为

p_1,p_2,\ldots,p_k,\ldots

当内层循环第一次枚举到满足

p_k\mid i

的质数 p_k 时，由于 primes 按照从小到大的顺序保存质数，所以 p_k 一定是 i 的最小质因子。

令 \ \ t=\frac{i}{p_k} 则\ i=t\times p_k

此时，代码已经标记了

i\times p_k=t\times p_k^2

这个数的最小质因子仍然是 p_k，所以这次标记是符合要求的。

接下来考虑：如果此处不执行 break，而是继续枚举下一个质数 p_{k+1}，代码将会标记

i\times p_{k+1} =t\times p_k\times p_{k+1}

因为 p_k<p_{k+1}，且 p_k 能够整除这个合数，所以它的最小质因子不是 p_{k+1}，而是 p_k。因此，它不应该在当前通过 i\times p_{k+1} 被标记。

事实上，这个数可以改写为

i\times p_{k+1} =\left(t\times p_{k+1}\right)\times p_k

由于

t\times p_{k+1}>t\times p_k=i

外层循环以后一定会枚举到 t\times p_{k+1}，届时再由它的最小质因子 p_k 完成标记即可。

如果当前不停止，那么这个合数会先被 p_{k+1} 标记一次，以后又被 p_k 标记一次，产生重复。因此，当第一次出现 i % p == 0 时，必须结束内层循环。

一个具体例子

假设当前 i=6。6 的最小质因子是 2。

当 p=2 时，代码标记

6\times 2=12

由于 6 % 2 == 0，内层循环在此停止。

如果不停止并继续枚举 p=3，就会标记

6\times 3=18

但是，18 的最小质因子是 2，所以它应该在外层循环枚举到 9 时，通过

9\times 2=18

被标记，而不应该在 i=6 时通过 6\times 3 被提前标记。break 正是避免了这一次重复操作。

六、为什么 p 不能整除 i 时可以继续？

设 q 是 i 的最小质因子。在内层循环第一次遇到 q 之前，当前枚举的质数 p 一定满足

p<q

由于 i 不含有比 q 更小的质因子，因此 i\times p 的最小质因子恰好就是 p。所以，在 i % p != 0 时使用 p 标记 i\times p 是正确的，内层循环可以继续。

例如，当 i=5 时：

5\times 2=10

其中 2 是 10 的最小质因子；

5\times 3=15

其中 3 是 15 的最小质因子；

5\times 5=25

其中 5 是 25 的最小质因子。

当枚举到 p=5 时，5 % 5 == 0，因此停止。如果继续枚举 7，那么 5\times 7=35 的最小质因子仍然是 5，它应当在外层循环枚举到 7 时通过 7\times 5 被标记。

因此，可以这样理解：

在遇到能够整除 i 的第一个质数之前，当前质数 p 是 i\times p 的最小质因子；遇到之后，更大的质数都不再是相应乘积的最小质因子，所以必须停止。

七、为什么每个合数一定会被标记，而且只被标记一次？

上面的分析说明了为什么需要 break。下面再从整体上说明线性筛的正确性。

任取一个合数 x，设它的最小质因子为 p，并令

i=\frac{x}{p}

于是

x=i\times p

由于 p 是 x 的最小质因子，i 不可能含有比 p 更小的质因子；否则这个更小的质因子也能整除 x，与 p 最小矛盾。因此，i 的最小质因子一定大于或等于 p。

所以，当外层循环枚举到 i 时，内层循环一定能够枚举到 p，并在停止之前执行

vis[i * p] = true;

从而标记 x。

另一方面，p 是 x 唯一的最小质因子，而与它对应的

i=\frac{x}{p}

也是唯一确定的。因此，每个合数都会被标记，并且只会由自己的最小质因子标记一次。

八、时间复杂度

在线性筛中，每次真正执行

vis[i * p] = true;

都会标记一个此前不会以其他方式重复标记的合数。因为不超过 n 的合数只有 O(n) 个，所以所有内层循环中有效标记操作的总次数也是 O(n)。

总结

线性筛最核心的规则是：

每个合数只由它的最小质因子标记一次。

代码中的

if (i % p == 0) break;

表示当前已经枚举到了 i 的最小质因子。如果继续使用更大的质数 q 标记 i\times q，那么 i\times q 的最小质因子仍然是当前的 p，它将在后续被 p 再次标记，从而产生重复。

因此，break 并不是一个单纯的代码技巧，而是保证“每个合数只由最小质因子筛一次”的关键。