线性筛（欧拉筛）
数学与数论 · 素数筛 · 每合数划一次 · O(N)
埃氏筛的浪费
埃拉托斯特尼筛 已经很快，但它有个小浪费：同一个合数会被好几个素数重复划掉。比如 12 会在处理 2 时被划（2×6）、在处理 3 时又想划（3×4）。这些重复让它停在 O(N log log N) 而非严格线性。线性筛（欧拉筛）补上这一刀——让每个合数只被划一次，做到严格 O(N)。
只被最小质因子划一次
关键改动：外层 i 不再只跳素数，而是遍历 2..N 的每一个数；对已经找到的每个素数 p（从小到大），划掉 i × p，并在 i % p == 0 时立即停。为什么这个 break 就够了？因为当 i % p == 0 时，p 是 i 的最小质因子；再往后用更大的 p' 去划 i × p'，那个数的最小质因子其实是 p（藏在 i 里），本该由后面某个 i' 来划——所以现在停手，就保证了每个合数 i × p 的最小质因子恰是 p，且只在这一刻被划这一次。
下面固定 N = 30（和埃氏筛同一张网格，方便对比）。点「下一步」逐步看：琥珀环是当前 i（注意它会停在合数上，因为外层遍历所有数）、红色是这一步划掉的 i × p，每个合数右下角标注划它的那个素数（=它的最小质因子）。走到底，10 个素数，且全网格没有一个合数被划第二次。右侧代码随每一步同步高亮。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
数字 1..30 排成网格（与埃氏筛同一张）；线性筛外层 i 遍历每个数，让每个合数只被它的最小质因子划一次
1function linearSieve(n: number): { primes: number[]; spf: number[] } {
2 const isComp = new Array(n + 1).fill(false);
3 const spf = new Array(n + 1).fill(0);
4 const primes: number[] = [];
5 for (let i = 2; i <= n; i++) {
6 if (!isComp[i]) primes.push(i); // i 没被划 → 素数
7 for (const p of primes) {
8 if (i * p > n) break; // 越界停
9 isComp[i * p] = true; // 划掉 i×p（只此一次）
10 spf[i * p] = p; // 它的最小质因子就是 p
11 if (i % p === 0) break; // p 是 i 的最小质因子 → 停
12 }
13 }
14 return { primes, spf };
15}
范围1..30
已确认素数0
1 / 13
为什么恰好线性
遍历所有 i：外层不只跳素数，2..N 每个数都作一次「乘数」。
i % p == 0 就停：保证 i×p 的最小质因子是 p，不越界替别人划。
每合数一次：每个合数被且仅被它的最小质因子划一次 → 总操作数 = 合数个数 = O(N)。
顺带：过程中还免费得到每个数的最小质因子表，质因数分解 O(log x) 即得。
i % p == 0 就停：保证 i×p 的最小质因子是 p，不越界替别人划。
每合数一次：每个合数被且仅被它的最小质因子划一次 → 总操作数 = 合数个数 = O(N)。
顺带：过程中还免费得到每个数的最小质因子表，质因数分解 O(log x) 即得。
线性筛的真正威力在于它能顺带批量计算积性函数：把 i % p == 0 与否两种情况的递推挂上去，欧拉函数 φ、莫比乌斯函数 μ、约数个数 d 等都能在同一趟 O(N) 里全部算出——这正是它比埃氏筛更受竞赛青睐的原因。