埃氏筛与线性筛：两种筛法详解
基于通用数论套路 · 核于 2026-07
速查
- 埃氏筛思路：从 2 起，每遇到一个仍标记为素数的
p，就把p的所有倍数2p、3p、...标记为合数——素数「划掉」自己的倍数。 - 埃氏筛复杂度：O(n log log n)（调和级数 ∑ 1/p，p 取素数，增长极慢，
n=10⁷时约3，几乎线性）。 - 埃氏筛的重复问题：一个合数会被它的所有素因子各筛一次——如
12被2（12=2×6）和3（12=3×4）各筛一次，30被2、3、5筛三次。 - 线性筛核心约束：让每个合数只被它的最小质因子筛掉一次——通过
i % p === 0时break实现。 - 线性筛的
break为何有效：设i = p × k（p是i的最小质因子），对更大的素数q > p，合数i × q = p × (k × q)的最小质因子仍是p而非q，应留给「外层 =k×q、内层素数 =p」那次来筛，故此时必须break。 - 线性筛复杂度：严格 O(n)——每个合数只被访问一次；空间额外 O(π(n)) 存素数表（π(n) 为 ≤n 的素数个数，约
n/ln n）。 - 关键代码差异：埃氏筛内层
for (k = 2p; k ≤ n; k += p)；线性筛内层遍历素数表且if (i % p === 0) break。 - 外层边界：埃氏筛外层只需到
√n（更大的素数p其p² > n，无 ≤n 的倍数可筛）；线性筛外层必须到n。 - 空间：两者均需 O(n) 的标记数组；线性筛额外 O(n/ln n) 的素数表。
- 易错：内层起点
2p而非p（p自己是素数不能删）；线性筛漏break会退化且重复；isPrime[0]=isPrime[1]=false必须初始化。 - 选型：
n ≤ 10⁷埃氏筛常数小通常更快；n更大或理论分析要求严格线性时用线性筛。
一、埃氏筛：素数划掉自己的倍数
埃拉托斯特尼筛（Sieve of Eratosthenes）是最古老也最直观的筛法。思路一句话：每个素数 p 把它的所有倍数标成合数。因为合数 k 一定有某个素因子 p，当外层遍历到 p 时，k（作为 p 的倍数）必然被标记——所以遍历结束后，仍为 true 的就是素数。
function eratosthenes(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false; // 0、1 不是素数
for (let p = 2; p * p <= n; p++) { // 外层只需到 √n
if (!isPrime[p]) continue; // p 是合数（已被更小素数筛掉），跳过
for (let k = p * p; k <= n; k += p) // 从 p² 开始筛（更小倍数已筛）
isPrime[k] = false;
}
return isPrime;
}注意两处优化：①外层只到 √n（p > √n 时 p² > n，没有 ≤n 的倍数可筛）；②内层从 p² 开始而非 2p（2p、3p、...(p-1)p 这些倍数在筛更小素数时已经标过了）。
复杂度：O(n log log n)
总标记次数是 ∑ₚ n/p（p 取素数）= n × (1/2 + 1/3 + 1/5 + 1/7 + ...)。素数倒数和约等于 ln ln n + M（M 为 Meissel-Mertens 常数），所以总次数约 n ln ln n，即 O(n log log n)。log log n 增长极慢：
| n | log log n（约） |
|---|---|
| 10⁶ | 2.6 |
| 10⁹ | 3.0 |
所以实际中埃氏筛「几乎线性」，常数又小，是绝大多数场景的首选。
二、埃氏筛为什么有重复
埃氏筛的代价是一个合数会被多次标记。设合数 m = p₁ × p₂ × ...，则对它的每一个素因子 pᵢ，外层遍历到 pᵢ 时都会把 m（作为 pᵢ 的倍数）标一次。以 12 为例：
m = 12 = 2² × 3
外层到 p=2：标 4, 6, 8, 10, 12, ... → 12 被标第 1 次
外层到 p=3：标 9, 12, 15, ... → 12 被标第 2 次12 被素因子 2 和 3 各筛一次。倍数素因子越多，重复越严重——30 = 2×3×5 被筛三次。这些重复标记虽然不影响正确性（多标几次 false 还是 false），但拉高了常数项，使复杂度从 O(n) 退化到 O(n log log n)。线性筛的目标就是消除这些重复。
三、线性筛：每个合数只筛一次
线性筛（又称欧拉筛）通过一个精巧的约束——每个合数只被它的最小质因子筛掉——保证每个合数恰好被标记一次，从而达成严格 O(n)。它额外维护「已知素数表 primes」，对外层数 i（从 2 到 n），遍历 primes 里的每个素数 p，筛掉合数 i × p；一旦 i 能被 p 整除就 break。
function linearSieve(n) {
const isPrime = new Array(n + 1).fill(true);
const primes = [];
isPrime[0] = isPrime[1] = false;
for (let i = 2; i <= n; i++) {
if (isPrime[i]) primes.push(i); // i 是素数，登记入表
for (let j = 0; j < primes.length; j++) {
const p = primes[j];
if (p * i > n) break; // 合数超出范围
isPrime[p * i] = false; // 筛掉 i × p
if (i % p === 0) break; // 关键：保证只被最小质因子筛
}
}
return primes;
}为何 i % p === 0 时必须 break
这是线性筛正确性的核心。设 i 能被 p 整除，即 i = p × k（此时 p 是 i 的最小质因子）。考虑素数表里 p 之后的更大素数 q > p，若不 break 继续筛 i × q：
i × q = p × k × q这个合数的最小质因子是 p（因为 p < q 且 p 整除它），不是 q。按「只被最小质因子筛」的约定，它应该留给「外层 i' = k × q、内层素数 p」那一次来筛（届时 i' × p = k × q × p = i × q）。如果现在用 q 筛了它，等 i' = k × q 时又会用 p 再筛一次——重复！
所以 break 的本质是：「既然 p 已经是 i 的因子，那么 i × (比 p 大的素数) 的最小质因子都是 p 而非那个大素数，应统一留给 p 来筛。」 这保证每个合数只在「最小质因子 × 某个数」的形式下被访问一次。
复杂度：严格 O(n)
由于每个合数 m 只在其 m = (最小质因子) × i 的唯一形式下被标记一次，内层总标记次数恰为 n 量级；外层 i 从 2 到 n。总体 O(n)。代价是空间多了素数表（O(n/ln n)），且常数（素数表访问、break 判断）大于埃氏筛——所以小数据下埃氏筛往往更快，线性筛的优势在 n 极大或理论分析时才显现。
四、两种筛法对照
| 维度 | 埃氏筛 | 线性筛（欧拉筛） |
|---|---|---|
| 思路 | 素数 p 筛 p 的倍数 | 每个合数只被最小质因子筛 |
| 复杂度 | O(n log log n) | O(n) |
| 是否重复 | 有（每个素因子各筛一次） | 无（每个合数筛一次） |
| 外层范围 | 到 √n 即可 | 必须到 n |
| 内层起点 | p²（优化）或 2p | p × i（遍历素数表） |
| 关键判断 | 无 | i % p === 0 时 break |
| 空间 | O(n)（标记数组） | O(n) + O(n/ln n)（素数表） |
| 常数 | 小（更快） | 大（额外素数表与判断） |
| 适用 | 通用首选、n ≤ 10⁷ | 严格线性、n 极大或积性函数筛 |
记忆口诀：「埃氏筛：素数筛倍数，简单但重复；线性筛：最小质因子筛一次，严格 O(n) 但常数大。」
交互演示
下一步
掌握两种筛法后，下一步看优化技巧与实际应用——从 p² 起筛省一半常数、用筛法预处理的素数表做 O(1) 查询、用最小质因子表 spf 做 O(log n) 质因数分解，以及何时该选哪种筛，见优化与应用场景。