埃拉托斯特尼筛
数学与数论 · 素数筛 · O(N log log N)
一次筛出所有素数
判断一个数是不是素数（只能被 1 和自己整除），最朴素的办法是拿它去试除 2..√x。但如果要找出 1..N 里所有素数，一个个试除就慢了。埃拉托斯特尼筛（公元前 3 世纪的古老算法）换了个思路——不去判断谁是素数，而是划掉谁一定不是：把 2..N 排开，从最小的开始，每遇到一个还没被划掉的数，它就是素数，然后把它的所有倍数都划掉（它们都是合数）。
两个关键优化
划倍数时，从 p² 开始就够了——因为 2p, 3p, …, (p−1)p 这些更小的倍数，早在处理 2, 3, …, p−1 时就被划掉了。而且外层只要跑到 p² > N 就能停：任何 ≤ N 的合数，必有一个 ≤ √N 的质因子，所以走到 √N 时所有合数都已被划完，剩下没划掉的全是素数。整体复杂度 O(N log log N)，几乎线性。
下面固定 N = 30。点「下一步」逐步看：绿色是确认的素数、灰色划掉是合数、琥珀环是当前正在处理的素数 p、红色是这一步正在划掉的 p 的倍数。处理完 2、3、5 后，7² = 49 > 30 就停了，剩下 7, 11, …, 29 一次性确认为素数。走到底，1..30 共 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 排成网格；1 既不是素数也不是合数；从 2 开始，每找到一个还没被划掉的数就是素数，再划掉它的所有倍数
1function sieve(n: number): number[] {
2 const isComposite = new Array(n + 1).fill(false); // 初始都没划掉
3 const primes: number[] = [];
4 for (let p = 2; p <= n; p++) {
5 if (!isComposite[p]) { // p 没被划掉 → 素数
6 primes.push(p);
7 for (let m = p * p; m <= n; m += p) // 从 p² 起划掉 p 的倍数
8 isComposite[m] = true;
9 }
10 }
11 return primes; // 剩下没划掉的都是素数
12}
范围1..30
已确认素数0
1 / 9
为什么这么快
不判断、只划掉：每个素数把自己的倍数标成合数，剩下的自然是素数。
从 p² 起：更小的倍数已被更小的素数划过，不用重复。
筛到 √N 即停：合数必有 ≤√N 的质因子，走到 √N 就全划完了。
复杂度：
从 p² 起：更小的倍数已被更小的素数划过，不用重复。
筛到 √N 即停：合数必有 ≤√N 的质因子，走到 √N 就全划完了。
复杂度：
O(N log log N)，比逐个试除的 O(N√N) 快得多。 埃氏筛是数论算法的基石：预处理出素数表后，质因数分解、欧拉函数、莫比乌斯函数等都能批量算。它的进阶版线性筛（欧拉筛）让每个合数只被它的最小质因子划一次，把复杂度压到严格 O(N)——那是这条线的下一站。