核心思想

埃氏筛（Eratosthenes Sieve）的效率瓶颈在于：一个合数可能会被其不同的质因子多次重复筛除。例如： $12$ 既会被 $2$ 筛去 ( $2 \times 6$ )，也会被 $3$ 筛去 ( $3 \times 4$ )。这种重复操作增加了不必要的计算冗余。

欧拉筛（Linear Sieve）的核心思想非常简单且强力：

确保每个合数只被它的“最小质因子”筛除一次。

为了实现这一点，我们需要在筛的过程中维护两个关键操作：

外层枚举：从小到大枚举数值 $i$ 。
内层标记：枚举已有的素数 $prime[j]$ ，标记 $i \times prime[j]$ 为合数。
关键中断：当发现 $i$ 已经被某个素数 $prime[j]$ 整除时，立即停止后续标记（Break）。

数学解析：唯一性分解的证明

为了证明算法的线性时间复杂度（不重复筛选），我们需要建立合数与筛选操作之间的一一映射关系。

定义

设 $n$ 为任意大于 1 的整数，定义函数 $L(n)$ 为 $n$ 的最小质因子（Least Prime Factor）。对于任意合数 $x$ ，我们可以将其唯一分解为两个整数的乘积：

x = L(x) \times M(x)

其中：

$L(x)$ 是 $x$ 的最小质因子。
$M(x) = x \div L(x)$ 是除以最小质因子后的商。

我们的目标是：对于任意合数 $x$ ，只在枚举到 $i = M(x)$ 且素数 $p = L(x)$ 时，才去标记 $x$ 。

证明：一一映射的存在性与唯一性

参考单射、满射与双射的定义-维基百科

为了证明算法既不漏（覆盖所有合数）又不重（线性复杂度），我们需要证明“筛选操作”与“合数”之间存在双向的一一对应关系。

定义映射 $f: (i, p) \to x$ ，其中 $(i, p)$ 为算法产生的合法配对， $x$ 为被筛掉的合数。

1. 存在性证明（对应“不漏”,满射）

命题：对于任意合数 $x$ ，存在一对符合欧拉筛规则的 $(i, p)$ 生成它。
证明：由算术基本定理，任意合数 $x$ 必有一个最小质因子 $L(x)$ 。令 $p = L(x), i = x/p$ 。显然 $p \le L(i)$ 成立（否则 $p$ 不是最小质因子）。因此，每一个合数 $x$ 都能被算法生成的某对 $(i, p)$ 筛掉。

2. 唯一性证明（对应“不重”,单射）

命题：对于任意合数 $x$ ，生成它的 $(i, p)$ 是唯一的。
证明：假设 $x$ 能被 $(i_1, p_1)$ 和 $(i_2, p_2)$ 两次筛掉，且都满足欧拉筛规则（即 $p$ 是 $i \times p$ 的最小质因子）。
- 这意味着 $p_1$ 是 $x$ 的最小质因子， $p_2$ 也是 $x$ 的最小质因子。
- 由最小质因子的唯一性，得 $p_1 = p_2$ 。
- 进而 $i_1 = x/p_1 = x/p_2 = i_2$ 。
- 故 $(i_1, p_1)$ 与 $(i_2, p_2)$ 是同一对。
结论：每个合数只会被其“最小质因子”筛去一次，绝无重复。

这篇文章在上一版的基础上，补充了你强调的**“性质推导”和“集合选择”**的逻辑，着重解决了从“数学定义”到“算法实现”的过渡，让“为什么要在 i % p == 0 时 break”这一行为有了严密的数学依据。

以下是完善后的文章：

2. 核心原理与证明

核心思想：唯一性筛选

欧拉筛（Linear Sieve）的核心思想非常简单且强力：

确保每个合数只被它的“最小质因子”筛除一次。

为了实现这一点，我们需要在筛的过程中维护两个关键操作：

外层枚举：从小到大枚举数值 $i$ （作为最大因子的候选者）。
内层标记：枚举已有的素数 $P_j$ ，将 $i \times P_j$ 标记为合数。
关键中断：当发现 $i$ 已经被某个素数 $P_j$ 整除时，立即停止后续标记（Break）。

数学解析：建立一一映射

为了证明算法的线性时间复杂度（即每个合数只被筛一次），我们需要建立合数与“筛选操作”之间的一一映射关系。

1. 定义与分解

设 $n$ 为任意大于 1 的整数，定义函数 $L(n)$ 为 $n$ 的最小质因子（Least Prime Factor）。

对于任意合数 $x$ ，我们可以将其唯一分解为两个整数的乘积：

x = M(x) \times L(x)

其中：

$L(x)$ 是 $x$ 的最小质因子（筛选时的素数 $p$ ）。
$M(x) = x \div L(x)$ 是除以最小质因子后的商（筛选时的倍数 $i$ ）。

我们的目标是：对于任意合数 $x$ ，只在枚举到 $i = M(x)$ 且素数 $p = L(x)$ 时，才去标记 $x$ 。

2. 证明：一一映射的存在性与唯一性

命题：每个合数 $x$ 仅对应唯一的一对 $(i, p)$ ，满足 $x = i \times p$ 且 $p = L(x)$ 。反之，符合特定条件的每一对 $(i, p)$ 也唯一生成一个合数。

证明：

存在性：由算术基本定理可知，任何合数 $x$ 都有唯一的质因数分解，必然存在一个最小的质因子。令 $p = L(x)$ ，令 $i = x / p$ 。显然 $i \times p = x$ 且 $p$ 是 $x$ 的最小质因子。因此，该组合 $(i, p)$ 存在。
唯一性：假设存在两对不同的组合 $(i_1, p_1)$ 和 $(i_2, p_2)$ 都能筛选出 $x$ ，且都遵循欧拉筛规则（即 $p$ 必须是 $x$ 的最小质因子）。根据定义， $p_1 = L(x)$ 且 $p_2 = L(x)$ 。因为一个数的最小质因子是唯一的，所以 $p_1 = p_2$ 。又因为 $i_1 \times p_1 = x$ 且 $i_2 \times p_2 = x$ ，推导出 $i_1 = i_2$ 。故分解方式是唯一的。

算法推导：如何确定 $p$ 的集合？

有了上述映射关系，接下来的核心问题是： 当我们枚举到一个具体的数 $i$ 时，应该用哪些素数 $p$ 去和它配对？

我们需要找到满足条件的素数集合 $\{p\}$ ，使得生成的合数 $x = i \times p$ 满足 $L(x) = p$ 。

性质推导

为了保证 $p$ 是 $x = i \times p$ 的最小质因子，必须满足以下限制：

限制条件：

p \le L(i)

证明：假设我们选用的素数 $p > L(i)$ 。那么合数 $x = i \times p$ 的因子包含 $i$ 的所有因子和 $p$ 。因为 $i$ 包含一个质因子 $L(i)$ ，且已知 $p > L(i)$ 。所以 $x$ 的最小质因子 $L(x)$ 将会是 $L(i)$ ，而不是 $p$ 。这就违背了“ $p$ 必须是 $x$ 的最小质因子”的前提。

因此，对于固定的 $i$ ，我们只能枚举 小于等于 $i$ 的最小质因子 的那些素数。

实例演示 ( $i=9$ )

假设当前枚举到 $i = 9$ 。 $9$ 的质因数分解为 $3 \times 3$ ，所以 $L(9) = 3$ 。根据限制条件 $p \le L(9)$ ，即 $p \le 3$ 。

已有的素数表为 primes = [2, 3, 5, 7, ...] 。

枚举 $p=2$ ：
- $2 < 3$ ，满足条件。
- 筛掉 $x = 9 \times 2 = 18$ 。
- 验证： $18$ 的最小质因子确实是 $2$ 。✅
枚举 $p=3$ ：
- $3 = 3$ ，满足条件。
- 筛掉 $x = 9 \times 3 = 27$ 。
- 验证： $27$ 的最小质因子确实是 $3$ 。✅
- 触发边界：发现 $i \% p == 0$ （ $9 \% 3 == 0$ ），说明 $p$ 已经达到了 $L(i)$ 的上限。
若强行枚举 $p=5$ （反例）：
- $5 > 3$ ，违反条件。
- 若筛掉 $x = 9 \times 5 = 45$ 。
- $45$ 的最小质因子是 $3$ （来自 $9$ ），而不是我们当前使用的 $5$ 。
- 这意味着 $45$ 应该在未来当 $i = 15$ ( $15 \times 3$ ) 时被筛除，而不是现在。❌

补充性质： $i \ge p$

在欧拉筛的运行过程中，生成的合数分解 $x = i \times p$ 总是满足 $i \ge p$ 。

证明：因为 $p$ 是 $x$ 的最小质因子。而 $i = x / p$ 是 $x$ 的一个因子。 $i$ 的所有质因子必然都大于等于 $x$ 的最小质因子 $p$ 。因此 $i \ge p$ 恒成立。 (注：这解释了为什么欧拉筛不会“回头”去筛比当前素数更小的范围)

算法演进：从重复到唯一

1 朴素的“倍数法”（存在重复）

我们先看一段试图用 $i$ 和 $p$ 组合筛选的代码，但不加任何限制。这对应了你的草稿中的代码：

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        std::vector<int> primes;
bool st[MAX_N];

void get_primes_naive(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.push_back(i); // i 是素数
        
        // 枚举已有的素数 p，构造合数 i * p
        for (auto p : primes) {
            if (p * i > n) break; // 越界停止
            
            st[p * i] = true; // 标记合数
            
            // 调试输出：观察谁筛掉了谁
            // printf("[%d] = %d x %d\n", p * i, p, i);
        }
    }
}

问题分析：以 $12$ 为例，该代码会执行两次标记：

当 $i=4$ 时，枚举到 $p=3$ （此时 primes 中有 2, 3）。计算 $4 \times 3 = 12$ 。虽然标记了 12，但此时使用的素数 $3$ 不是 $12$ 的最小质因子（ $2$ 才是）。
当 $i=6$ 时，枚举到 $p=2$ 。计算 $6 \times 2 = 12$ 。此时 $2$ 是 $12$ 的最小质因子。

这就违反了“一一映射”原则，导致了重复计算。

2 欧拉筛的修正（引入 Break）

为了修正上述问题，我们必须保证构造 $x = i \times p$ 时， $p$ 必须小于等于 $i$ 的最小质因子。

核心修正逻辑：在内层循环枚举素数 $p$ 时，如果发现 i % p == 0，说明 $p$ 是 $i$ 的因子（且由于是从小到大枚举， $p$ 必然是 $i$ 的最小质因子）。此时，必须停止枚举更大的素数并 Break。

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

        void get_primes_euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.push_back(i);
        
        for (int j = 0; j < primes.size(); j++) {
            int p = primes[j];
            if (i * p > n) break;
            
            st[i * p] = true;
            
            // 【核心关键】
            // 如果 i 被 p 整除，说明 i 的最小质因子就是 p。
            // 如果继续枚举下一个素数 p_next (p_next > p)，
            // 构造出的合数 X = i * p_next。
            // X 的最小质因子将会是 p (因为 i 包含因子 p)，而不是 p_next。
            // 这违背了“用最小质因子筛除”的原则，因此必须 break。
            if (i % p == 0) break;
        }
    }
}

为什么 `i % p == 0` 时必须 Break？

我们可以通过反证法来理解这个 Break 的必要性。

假设当 i % p == 0 时，我们不停止，继续枚举下一个更大的素数 $p'$ （即 $p' > p$ ）。我们要筛除的合数是 $X = i \times p'$ 。

因为 $i$ 是 $p$ 的倍数，可以设 $i = k \times p$ 。那么：

X = i \times p' = (k \times p) \times p' = (k \times p') \times p

请注意 $X$ 的质因子分解。因为 $p < p'$ ，所以 $X$ 的最小质因子肯定是 $p$ （或者比 $p$ 更小），绝对不可能是 $p'$ 。

但在当前的循环中，我们是试图用 $p'$ 作为筛选因子来筛掉 $X$ 。这意味着我们违反了“让每个合数只被它的最小质因子筛除”的规定。这个 $X$ 应该由谁来筛？它应该在未来，当外层循环枚举到 $i_{new} = k \times p'$ 时，被素数 $p$ 筛掉。

例子：当 $i=4$ ，primes 为 $\{2, 3\}$ 。

$p=2$ ： $4 \times 2 = 8$ 。 $8$ 的最小质因子是 $2$ ，合法。标记 $8$ 。检测 4 % 2 == 0，触发 Break。
假如不 Break，继续 $p=3$ ：计算 $4 \times 3 = 12$ 。对于 $12$ 来说，最小质因子是 $2$ 。但这里我们试图用 $3$ 去筛它。这就是多余的操作。 $12$ 应该在 $i=6$ 时，由 $6 \times 2$ 筛除。

总结

欧拉筛通过简单的 if (i % p == 0) break; 实现了对合数分解唯一性的严格控制：

当 i % p != 0：说明 $p$ 小于 $i$ 的所有质因子。此时 $p$ 必定是 $i \times p$ 的最小质因子。继续筛选。
当 i % p == 0：说明 $p$ 是 $i$ 的最小质因子。此时 $i \times p$ 的最小质因子是 $p$ 。但如果换用更大的素数 $p'$ ，合数 $i \times p'$ 的最小质因子依然是 $p$ （来自 $i$ ），而不是 $p'$ 。为了避免重复，必须停止。

目录