图 1：本文封面，合数不用算，标记就行。
先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面朴素：输出 2 到 2000 之间的所有素数，怎么写得尽量快？
先把结论立住：**别逐个验算素数，反过来标记合数——从小到大每遇到一个没被标记的数就是素数，把它的倍数划掉，剩下的就是答案。**这就是埃氏筛；再进一步，让每个合数只被它的最小质因子划一次，就是严格线性的欧拉筛；最后用位压缩把标记数组缩成一个比特一个数，内存与缓存命中双赢。三种写法加上试除基准，下面全部实测。
**为什么试除法慢？**对每个数 x 都从 2 试到 √x，2000 个数要做上万次除法；更根本的问题是它在「重复发现同一个事实」——6 是合数这件事，试除 6 时发现一次，试除 12、18 时又一遍遍重新发现。筛法把这个事实只算一次：遇到 2 就一次性标记 4、6、8、10……答案不在计算里，在标记里。
**埃氏筛的两个加速点。**一是划倍数从 i² 开始而不是 2i——更小的倍数早被更小的素数划过了；二是外层循环遇到已标记的数直接跳过。它的复杂度约为 O(n log log n)，已经足够快，但存在重复标记：6 会被 2 划一次、被 3 再划一次，12 被 2 和 3 各划一次。
**欧拉筛消掉重复标记。**维护一张素数表，遍历到 i 时只用素数表里的素数 p 去标记 i×p，一旦 i 能被 p 整除立即停手——因为此时 i×(更大的素数) 的最小质因子都是 p，往后标也是重复劳动。这样每个合数恰好被它的最小质因子划掉一次，复杂度严格 O(n)。
**位压缩是工程层的最后一挤。**布尔标记改用一个比特存一个数，2000 个数只需 251 字节左右，标记数组全在一两 cache line 里，连内存带宽都省了。
图 2：埃氏筛会重复标记，欧拉筛每个合数只标一次。
三种写法加试除基准，用 Node.js 22.15.0 直接运行（node sieve.js），先对齐 2 到 2000 的正确性，再放大到一千万看速度差：
'use strict';
// 试除法：每个数都从头验算，作为正确性基准
function trialDivision(n) {
const primes = [];
outer: for (let x = 2; x <= n; x++) {
for (let d = 2; d * d <= x; d++) if (x % d === 0) continue outer;
primes.push(x);
}
return primes;
}
// 埃氏筛：每遇到一个未标记的数就是素数，把它的所有倍数划掉
function eratosthenes(n) {
const composite = new Array(n + 1).fill(false);
const primes = [];
for (let i = 2; i <= n; i++) {
if (composite[i]) continue;
primes.push(i);
for (let j = i * i; j <= n; j += i) composite[j] = true;
}
return primes;
}
// 欧拉筛：每个合数只被它的最小质因子划掉一次
function euler(n) {
const composite = new Array(n + 1).fill(false);
const primes = [];
for (let i = 2; i <= n; i++) {
if (!composite[i]) primes.push(i);
for (const p of primes) {
const x = i * p;
if (x > n) break;
composite[x] = true;
if (i % p === 0) break; // i 含因子 p，后面的素数乘 i 的最小质因子都是 p，停手
}
}
return primes;
}
// 位压缩埃氏筛：一个比特存一个数，Uint8Array 当位图用
function eratosthenesBits(n) {
const bits = new Uint8Array(Math.ceil((n + 1) / 8));
const mark = (x) => { bits[x >>> 3] |= 1 << (x & 7); };
const isMarked = (x) => (bits[x >>> 3] >> (x & 7)) & 1;
const primes = [];
for (let i = 2; i <= n; i++) {
if (isMarked(i)) continue;
primes.push(i);
for (let j = i * i; j <= n; j += i) mark(j);
}
return { primes, bytes: bits.length };
}
const N = 2000;
const base = trialDivision(N);
const e1 = eratosthenes(N);
const e2 = euler(N);
const e3 = eratosthenesBits(N);
console.log(`2 到 ${N} 的素数共 ${base.length} 个`);
console.log(`前 10 个：${base.slice(0, 10).join(', ')}`);
console.log(`最后 5 个：${base.slice(-5).join(', ')}`);
console.log(`埃氏筛与试除一致：${e1.join() === base.join()}`);
console.log(`欧拉筛与试除一致：${e2.join() === base.join()}`);
console.log(`位压缩筛与试除一致：${e3.primes.join() === base.join()}，位图占 ${e3.bytes} 字节`);
// 放大到一千万，看重复标记的代价与位压缩的收益
const BIG = 10_000_000;
let t0 = performance.now();
const bigE = eratosthenes(BIG);
const tE = performance.now() - t0;
t0 = performance.now();
const bigL = euler(BIG);
const tL = performance.now() - t0;
t0 = performance.now();
const bigB = eratosthenesBits(BIG);
const tB = performance.now() - t0;
console.log(`n=${BIG.toLocaleString('en-US')}：埃氏筛 ${tE.toFixed(0)}ms，欧拉筛 ${tL.toFixed(0)}ms，位压缩埃氏筛 ${tB.toFixed(0)}ms`);
console.log(`三种算法结果一致：${bigE.length === bigL.length && bigL.length === bigB.primes.length}（共 ${bigE.length} 个素数）`);
实测输出：
2 到 2000 的素数共 303 个
前 10 个：2, 3, 5, 7, 11, 13, 17, 19, 23, 29
最后 5 个：1979, 1987, 1993, 1997, 1999
埃氏筛与试除一致：true
欧拉筛与试除一致：true
位压缩筛与试除一致：true，位图占 251 字节
n=10,000,000：埃氏筛 93ms，欧拉筛 66ms，位压缩埃氏筛 57ms
三种算法结果一致：true（共 664579 个素数）
一千万规模下欧拉筛比埃氏筛快约三成——这就是「重复标记」的真实代价；位压缩再快一截，靠的是标记数组缩进缓存。注意耗时是本机单次运行的量级参考，重点在相对差距而非绝对数字。
**常见误区。**一是埃氏筛内层从 2i 开始划，白做一半功；二是欧拉筛忘记 i % p === 0 就停手，退化成重复标记；三是标记数组开成 new Array(n).fill(false) 还嫌不够，上对象或 Map，内存和速度双输；四是把「尽量快」理解成上多线程，2000 这个量级启动开销都比计算贵。
跳出题目看，筛法「用空间换时间、标记代替重算」的思想和缓存预计算、倒排索引一脉相承，位压缩技巧在特征工程与布隆过滤器里同样常用。你第一次写筛法时踩的是哪个坑？欢迎分享。