一次性"筛"出一个范围内所有的质数，而不是对每个数都跑一遍 1.3 节的 IsPrime——模块一的最后一站。
1.3 节的 IsPrime 能很快判断一个数是不是质数。但如果题目要求"找出 1 到 100 万之间所有的质数"，对每个数都单独跑一遍 IsPrime，总共要做大约 100万 × √(100万) 次运算——这是一个非常大的数字，太慢了。
这一节换一个思路：不再一个一个去"问"每个数"你是不是质数"，而是反过来——每找到一个质数，就把它的所有倍数都标记成"不是质数"。标记完之后，没被标记过的数，自然就是质数。这种"批量打标记"的办法，就是筛法。
这是最早、最经典的筛法，叫埃拉托斯特尼筛法（简称埃氏筛）：从 2 开始，如果一个数还没被标记过，它就是质数，把它的倍数（2倍、3倍、4倍...）全部标记成"合数"；然后看下一个数，重复同样的操作。
| 1 | vector<int> Sieve(int n) |
| 2 | { |
| 3 | vector<bool> isComposite(n + 1, false); |
| 4 | vector<int> primes; |
| 5 | for (int i = 2; i <= n; i++) |
| 6 | { |
| 7 | if (!isComposite[i]) // 没被标记过，是质数 |
| 8 | { |
| 9 | primes.push_back(i); |
| 10 | for (int j = i * 2; j <= n; j += i) // 标记 i 的所有倍数 |
| 11 | { |
| 12 | isComposite[j] = true; |
| 13 | } |
| 14 | } |
| 15 | } |
| 16 | return primes; |
| 17 | } |
看一下第 3 步标记 5 的倍数时发生的事——5×2=10、5×3=15、5×4=20 这几个数，早就已经被 2 或 3 标记过了，重新标记一遍纯属浪费。其实可以直接从 5×5=25 开始标记——因为任何比 i×i 小的 i 的倍数，必然能写成"更小的数 × i"，而这个"更小的数"自己也是某个更小质数的倍数，早就被那个更小的质数标记过了。这个优化和 1.3 节"只检查到 √n"是同一个道理。
| 1 | vector<int> Sieve(int n) |
| 2 | { |
| 3 | vector<bool> isComposite(n + 1, false); |
| 4 | vector<int> primes; |
| 5 | for (int i = 2; i <= n; i++) |
| 6 | { |
| 7 | if (!isComposite[i]) |
| 8 | { |
| 9 | primes.push_back(i); |
| 10 | for (long long j = (long long)i * i; j <= n; j += i) |
| 11 | { |
| 12 | isComposite[j] = true; |
| 13 | } |
| 14 | } |
| 15 | } |
| 16 | return primes; |
| 17 | } |
i * i 要小心溢出：如果 n 比较大（比如十万以上），i 也可能达到几百，i * i 用 int 计算可能会超出范围。写成 (long long)i * i，先把其中一个数转换成 long long 再相乘，可以避免这个问题。i×i 开始标记，12 还是会被 2 标记一次（当 i=2 时），也会被 3 标记一次（当 i=3 时，但因为 12<3×3=9 不成立所以这次反而不会发生——这里只是想说明，合数被多个质数重复标记这件事，光靠"从 i×i 开始"是消除不掉的，只是减少了一部分）。下一节要解决的，正是这个"重复劳动"的问题。回头看 2~30 这个例子：12 被标记了两次——一次是 2 的倍数（2×6），一次是 3 的倍数（3×4）；30 更夸张，被 2、3、5 各标记了一次，一共三次。这些重复劳动加起来，让埃氏筛法没有真正做到"每个数只处理一次"。
线性筛（也叫欧拉筛）要解决的就是这个问题：让每一个合数只被标记一次——具体来说，只让它的"最小质因子"标记它，其他比这个更大的质因子，都不准再标记。
2×6 标记一次，又被 3×4 标记一次 —— 重复劳动了 1 次12 的最小质因子（也就是 2）标记它，3 不准再标记 —— 只标记 1 次具体怎么做到"只让最小质因子标记"？做法是：从小到大处理每一个数 i，把它和"目前已经找到的每一个质数"依次配对相乘，每配对出一个新的合数，就记下"这个合数的最小质因子是谁"。关键规则是：一旦配对用的质数超过了 i 自己的最小质因子，就立刻停止配对——因为再往下配对出来的那个合数，应该交给"i 自己的最小质因子"去标记，不该让现在这个更大的质数抢先标记。
3 配对 6 得到 18？因为 18 真正的最小质因子是 2（18=2×9），不是 3。如果这里放行，18 就会被"提早"标记成"最小质因子是 3"，等到后面 i=9 时，2×9=18 又会被正确地标记一次——同一个数被标记了两次，又走回了埃氏筛法的老问题。停在这里，恰恰是为了把 18 "让"给后面更合适的机会去标记。| 1 | vector<int> LinearSieve(int n) |
| 2 | { |
| 3 | vector<int> minPrimeFactor(n + 1, 0); // 0 表示还不知道 |
| 4 | vector<int> primes; |
| 5 | for (int i = 2; i <= n; i++) |
| 6 | { |
| 7 | if (minPrimeFactor[i] == 0) // 没被标记过，i 自己是质数 |
| 8 | { |
| 9 | minPrimeFactor[i] = i; |
| 10 | primes.push_back(i); |
| 11 | } |
| 12 | for (int j = 0; j < (int)primes.size(); j++) |
| 13 | { |
| 14 | int p = primes[j]; |
| 15 | if (p > minPrimeFactor[i] || (long long)p * i > n) |
| 16 | { |
| 17 | break; // 超过了i的最小质因子，停止配对 |
| 18 | } |
| 19 | minPrimeFactor[p * i] = p; |
| 20 | } |
| 21 | } |
| 22 | return primes; |
| 23 | } |
用 n = 1000 数一数两种筛法总共做了多少次标记：
12、30 那样被多个质数重复标记的浪费。| 写法 | 核心思路 | 时间复杂度 |
|---|---|---|
| 埃氏筛法 | 每找到一个质数，标记它的所有倍数 | O(n log log n) |
| 埃氏筛（优化） | 从 i×i 开始标记，跳过早被标记过的部分 | O(n log log n)，常数更小 |
| 线性筛 | 每个合数只由它的最小质因子标记一次 | O(n) |