SIEVE OF ERATOSTHENES · FROM ONE QUERY
埃氏筛法详解
判断一个正整数是否为素数，可以逐个试除；当查询数量增大时，判定之间互不共享的代价开始累积。 把“询问一个数”换成“标记一批合数”，素数表便在一次遍历中完成。
01 · 基本方案
单个数字的试除判定
素数定义、因数成对、试除到 √x、单次判定的代价。
大数素性测试（Miller–Rabin）只在最后一章提及，不进入主线。
素数的定义：只有两个正因数的正整数
素数定义：大于 1 且只有 1 和自身两个正因数的正整数。通俗地说，素数就是“拆不开”的数：不能写成两个大于 1 的正整数相乘（1 本身除外）。判定一个数 x 是否为素数，最直接的方案是检查 2 到 x−1 之间是否存在 x 的因数：存在则 x 是合数，不存在则 x 是素数。这个方案直接对照定义，一定正确。
因数成对：试除为什么只需要到 √x
若 x = a × b 且 a ≤ b，则 a ≤ √x。否则 a 与 b 都大于 √x，乘积将大于 x。 因此 2 到 √x 之间没有因数，就等价于 x 没有任何因数。
13 只需要试 2、3，因为 4² = 16 已经大于 13。36 = 4 × 9，因子对 (4, 9) 中较小者 4 不超过 √36 = 6。
| x | 因子对 | 需要试到 |
|---|---|---|
| 13 | (1,13) | 2, 3 |
| 36 | (2,18),(3,12),(4,9),(6,6) | 2,3,4,5,6 |
| 97 | (1,97) | 2..9 |
单次判定的代价：O(√x)
试除次数与 √x 成正比。对单个数字，问题已经解决；x 在 10¹² 量级时，√x = 10⁶，仍然可以接受。
02 · 痛点分析
重复劳动：多个查询的代价
批量查询时试除法的代价如何累积；本阶段不引入新数据结构，只改变看待问题的角度。
本节是视角转换，不产生可复用代码。
多个查询的代价：Q × √X
《素数伴侣》中，每个奇偶对都要查询“a + b 是否为素数”。n = 100 时最多 2500 对，和的最大值不超过 60000。
试除到 √60000 ≈ 245，2500 次查询约 6×10⁵ 次取模，小数据下并不慢；但查询数放大到 10⁵、和的上限放大到 10⁶ 时，代价变成 Q × √X，乘积增长。更本质的问题是：判断 13 时算出的“2、3 不能整除 13”，无法帮助判断 17；而“16 能被 2 整除”这个事实，本可以在检查 2 的时候就批量写下来。
重复劳动的来源：判定之间无法共享信息
每次判定都独立试除：判断 13 时算出的“2、3 不能整除 13”，无法帮助判断 17；而“16 能被 2 整除”这个事实，本可以在检查 2 的时候就批量写下来。判定之间互不共享，是重复劳动的结构性来源。
合数的定义：某个更小数字的倍数
严谨定义：合数是大于 1、并且除了 1 和自身之外还存在其他正因数的正整数。等价地，一个正整数是合数，当且仅当它能写成两个大于 1 的正整数的乘积。4 = 2×2、6 = 2×3、9 = 3×3 都是合数；2、3、5、7、11 不是合数。
通俗理解：合数就是“能拆成两个更小的正整数相乘”的数。能拆，意味着它一定是某个更小数字的倍数：6 同时是 2 和 3 的倍数，15 同时是 3 和 5 的倍数。
作用：这个“一定是谁的倍数”的性质让批量标记成为可能——与其逐个问 x 是不是素数，不如一次性回答：哪些数是 2 的倍数、哪些数是 3 的倍数、哪些数是 5 的倍数……把所有合数标记完后，剩下的数字天然是素数。
批量标记：预计算整除关系，查询降为 O(1)
03 · 独立章节
合数的最小质因子
合数的乘法结构、最小质因子、为什么每个合数都能被某个较小素数整除。
唯一分解定理的完整证明留作扩展。
概念定位：为什么这里需要最小质因子
合数的结构：质因数分解
每个合数 x 都可以分解成若干个素数的乘积，例如 12 = 2 × 2 × 3。这些质因子中有一个最小的，称为 x 的最小质因子。
为什么一定存在这样的分解（存在性，强归纳证明）：对 n > 1 归纳。n = 2 是素数，本身就是一个长度为 1 的分解。假设所有 1 < m < n 都已经能分解：若 n 是素数，分解就是 n 自己；若 n 是合数，由合数定义存在因数 a 满足 1 < a < n，令 b = n/a，则 1 < b < n；归纳假设给出 a、b 各自的素数分解，合并后就是 n 的分解。每一步要么直接结束，要么把数拆成两个更小的数，因此过程必然在有限步内停止。
为什么不计顺序时分解唯一（唯一性，算术基本定理）：唯一性依赖欧几里得引理——素数 p 若整除乘积 ab，则 p 必整除 a 或 b。用这条引理从两列质因子中逐次消去相同的素数，可以证明任意两种分解都只差顺序。欧几里得引理可由 Bézout 恒等式（p 与 a 互素时存在整数 x、y 使 ax + py = 1）推出。
质因子集合有限且非空，因此其中必有最小值，这就是最小质因子。它还是后面“筛法不会漏掉合数”论证的起点。
质因数分解的存在性、唯一性（欧几里得引理与 Bézout 恒等式）及最小质因子的全部证明与数值例子，见独立知识页： 合数与质因数分解：定义、性质与证明 →
| x | 质因数分解 | 最小质因子 |
|---|---|---|
| 4 | 2 × 2 | 2 |
| 6 | 2 × 3 | 2 |
| 9 | 3 × 3 | 3 |
| 12 | 2 × 2 × 3 | 2 |
| 25 | 5 × 5 | 5 |
合数的性质：最小质因子
x 是合数当且仅当存在素数 p < x 使得 p 整除 x。
最小质因子 p ≤ √x 设 x = p × m。若 m < p，则 m 含有小于 p 的质因子 q 且 q 整除 x，与 p 最小矛盾，故 m ≥ p；于是 x = p·m ≥ p²，即 p ≤ √x。等价地，若 x 的全部质因子都大于 √x，它们的乘积将大于 x。
每个合数 x都能被某个不超过 √x 的素数整除。
性质推论：合数必有不超过 √x 的质因子
04 · 批量标记
埃氏筛：标记所有合数
埃氏筛的执行过程、正确性论证、复杂度来源。
从 i² 开始、只筛奇数、线性筛分别留到后续章节。
筛法规则：素数的倍数全是合数
建表[2, n] 全部记为“可能是素数”。
标记从 2 开始：若当前数 p 尚未被标记，则 p 是素数，把 p 的所有倍数标记为合数。
推进移动到下一个未标记的数，重复，直到遍历完整个范围。
执行演示：n = 30 的标记过程
| 轮次 | 当前未标记数 | 判定 | 标记的倍数 |
|---|---|---|---|
| 1 | 2 | 素数 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 |
| 2 | 3 | 素数 | 6, 9, 12, 15, 18, 21, 24, 27, 30（大部分已标记） |
| 3 | 4 | 已标记，跳过 | — |
| 4 | 5 | 素数 | 10, 15, 20, 25, 30 |
| 5 | 6 | 已标记，跳过 | — |
| 6 | 7 | 素数 | 14, 21, 28 |
| 7 | 8..10 | 已标记，跳过 | — |
| 8 | 11 | 素数 | 范围内无新倍数 |
| 9 | 13, 17, 19, 23, 29 | 素数 | 范围内无新倍数 |
最终未标记的数是 2, 3, 5, 7, 11, 13, 17, 19, 23, 29，与素数表一致。
正确性论证：不漏与不误伤
任何合数 x 都有最小质因子 p ≤ √x；执行到 p 时，x 会被这一轮标记。
素数没有小于自身的因子，不会被任何一轮标记。
复杂度分析：为什么是 O(n log log n)
标记总次数等于每个素数 p 贡献的 n/p 次：n/2 + n/3 + n/5 + …。素数倒数和约为 log log n，因此总标记次数 ≈ n log log n，空间 O(n)。
| 方案 | 单次查询 | 批量查询 | 额外空间 |
|---|---|---|---|
| 试除法 | O(√x) | O(Q·√X) | O(1) |
| 埃氏筛 | O(1) 查表 | 预处理 O(n log log n) | O(n) |
12 同时是 2 和 3 的倍数，被标记两次；重复不影响正确性，但影响常数。n = 10⁷ 时布尔表约 10 MB，n = 10⁹ 时不能直接开表。
05 · 起点优化
起点优化：从 i² 开始标记
为什么 i 的倍数可以从 i² 开始，跳过了哪些重复工作。
本优化不改变复杂度阶，只压缩常数。
可预见的重复：更小的倍数已被更小的素数标记
2i 是 2 的倍数，在 2 那一轮已经被标记；3i 是 3 的倍数，在 3 那一轮已经被标记。一般地，ki（k < i）含有一个小于 i 的质因子，该质因子所在的轮次必然先于 i 执行。
优化效果：从 i² 开始，常数变小
从 i² 开始标记，每个素数 i 节省 (i−1) 次标记；总标记次数从约 n log log n 变成约 n log log n − O(n)，复杂度阶不变，常数变小。
重复标记仍然存在：12 > 3² 且含因子 2，在 3 的轮次仍会被标记。这说明“跳过小倍数”只去掉了部分重复。
06 · 空间优化
空间优化：只保留奇数
除 2 外所有偶数都是合数，存储可以压缩一半。
奇偶压缩需要下标映射，属于常数级优化。
偶数的性质：2 是唯一的偶素数
2 是唯一的偶素数，其余偶数全部是合数，不需要占用数组位。只存奇数 3, 5, 7, …，用下标 i 映射到数值 2i+1（或 2i+3），标记时跳过所有偶数。
压缩方案：下标映射只存奇数
优化掉了：一半的存储空间和一半的标记次数。代码需要维护“下标 ↔ 数值”的映射，可读性略降；内存紧张、范围很大时收益明显。若还需要最小质因子表，压缩会带来额外访问换算，通常不划算。
07 · 进阶加速
线性筛：每个合数只标记一次
埃氏筛的重复标记来源、线性筛的 break 条件、为什么每个合数恰好被最小质因子标记一次。
线性筛可顺带得到最小质因子表，用于质因数分解。
重复标记的来源：一个合数拥有多个质因子
埃氏筛中，12 被 2 和 3 各标记一次，18 被 2 和 3 各标记一次。重复来自“同一个合数被多个质因子各轮一次”。
线性筛方案：每个合数只交给最小质因子
维护一个已经筛出的素数表 primes。对每个 i 从 2 到 n，从小到大尝试 primes 中的素数 p，标记 i × p；一旦 p 整除 i，立即停止内层循环。
break 条件的证明：为什么恰好标记一次
任意合数 x 有唯一的最小质因子 p，记 i = x / p。此时 i 的所有质因子都不小于 p。当外层循环执行到 i 时，primes 中 p 之前的素数 q 都不整除 i，因此不会提前 break；逐个标记 i×q 后，轮到 p：x 被标记，且 p 整除 i，break。
任何更大的素数 p′ 不会标记 x：i × p′ 的最小质因子是 min(p′, i 的最小质因子)。若 p′ 较大，这个最小质因子来自 i，因此 i × p′ 应交给更小的组合标记，而不是 p′。
内层总执行次数等于合数个数加素数个数，整体线性。每个合数恰好被“自身 ÷ 最小质因子”这一组合标记一次。
埃氏筛已经以 O(n log log n) 解决“批量查素数”这一主要问题。线性筛是不同条件下的替代：需要严格线性复杂度，或需要最小质因子表时使用；只为查询素数表时，两者的实际差距通常不足以抵消线性筛稍复杂的逻辑。
08 · 模型迁移
应用：素数伴侣与质因数分解
素数伴侣的查表建图、最小质因子分解、区间筛。
筛选场景的识别顺序。
素数伴侣中的查表建图
问题变成：对每个奇偶对查询“a + b 是否为素数”，最多 2500 次，和上限 60000。筛表一次完成 O(n log log n) 预处理，此后每次查询是 O(1) 的布尔数组访问；建图逻辑从“每个组合现场试除”简化为“查表连边”。小数据下试除法也能通过，筛法的价值在于把查询成本与值的规模解耦，并让代码结构统一。
质因数分解中的最小质因子表
线性筛顺带记录每个数的最小质因子 lp[x]。分解 x 时反复执行 p = lp[x]、除尽 p，每步去掉一个质因子，总步数等于质因子个数（含重数），约 O(log x)。这在多个数分解、求欧拉函数 φ(1..n) 等场景中是标准工具。
区间筛：大范围窄区间的处理
当 R 很大（10⁹）但 R − L 很小（10⁶）时，不能直接开 [0, R] 的表。先用 √R 以内的素数筛出小表，再在 [L, R] 区间内用这些素数标记，空间只与区间长度有关。
筛法选型顺序
查询次数少 → 试除法；上界小且查询多 → 埃氏筛；内存紧张 → 奇偶压缩；需要线性或最小质因子表 → 线性筛；大范围窄区间 → 区间筛。
09 · 判断边界
筛法选型
试除、埃氏筛、奇偶压缩、线性筛、区间筛、Miller–Rabin 的适用边界。
Miller–Rabin 只作名称提示，不展开。
各方案的适用边界
| 场景 | 方案 | 理由 |
|---|---|---|
| 单个或少量查询 | 试除到 √x | 不需要预处理，常数最小 |
| 批量查询、上界 ≤ 10⁷ | 埃氏筛 | 一次预处理，查询 O(1) |
| 内存受限 | 奇偶压缩的埃氏筛 | 空间减半 |
| 需要最小质因子表 / 严格线性 | 线性筛 | 每个合数只标记一次 |
| R 大、R−L 小 | 区间筛 | 空间只与区间长度有关 |
| 单个超大随机数 | Miller–Rabin（扩展） | 试除与筛法都不适用 |
10 · 多语言实现
代码实现
Python、C、Java、C++ 四种实现，均从 i² 开始标记。
四种语言只在输入输出与内存管理上有差异，算法结构完全一致。
Python 实现
import math
def sieve(n: int) -> list[bool]:
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
n = int(input())
is_prime = sieve(n)
print(sum(is_prime[2:]))C 实现
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
bool *sieve(int n) {
bool *is_prime = malloc((n + 1) * sizeof(bool));
for (int i = 0; i <= n; ++i) is_prime[i] = true;
if (n >= 0) is_prime[0] = false;
if (n >= 1) is_prime[1] = false;
for (int i = 2; i * i <= n; ++i)
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
return is_prime;
}
int main(void) {
int n;
scanf("%d", &n);
bool *is_prime = sieve(n);
int cnt = 0;
for (int i = 2; i <= n; ++i) cnt += is_prime[i];
printf("%d\n", cnt);
free(is_prime);
return 0;
}Java 实现
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static boolean[] sieve(int n) {
boolean[] is_prime = new boolean[n + 1];
Arrays.fill(is_prime, true);
if (n >= 0) is_prime[0] = false;
if (n >= 1) is_prime[1] = false;
for (int i = 2; i * i <= n; ++i)
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
return is_prime;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
boolean[] is_prime = sieve(n);
int cnt = 0;
for (int i = 2; i <= n; ++i)
if (is_prime[i]) ++cnt;
System.out.println(cnt);
}
}C++ 实现
#include <bits/stdc++.h>
using namespace std;
vector<bool> sieve(int n) {
vector<bool> is_prime(n + 1, true);
if (n >= 0) is_prime[0] = false;
if (n >= 1) is_prime[1] = false;
for (int i = 2; i * i <= n; ++i)
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
return is_prime;
}
int main() {
int n;
cin >> n;
auto is_prime = sieve(n);
int cnt = 0;
for (int i = 2; i <= n; ++i) cnt += is_prime[i];
cout << cnt << '\n';
return 0;
}11 · 参考