优化与应用场景
基于通用数论套路 · 核于 2026-07
速查
- 从 p² 起筛：埃氏筛内层从
p²开始而非2p——更小的倍数2p、3p、...(p-1)p在筛更小的素因子时已经标过，省一半以上常数。 - 外层到 √n：埃氏筛外层
p只需到√n——更大的素数p² > n，没有 ≤n 的倍数可筛。 - 只筛奇数：单独处理 2 后，只对奇数开数组、只让奇素数筛奇倍数，空间和时间均减半（位压缩还能再除 8）。
- 位压缩：用
BitSet/ 位运算代替布尔数组，空间从 O(n) 字节降到 O(n/8) 字节——n = 10⁹时从 1GB 降到 125MB。 - 分段筛：
n超过内存容量时，把[1, n]分成若干段，逐段用[2, √n]内的素数筛——空间降到 O(√n + 段长)。 - 线性筛为何 O(n)：每个合数只在
m = 最小质因子 × i的唯一形式下被标记一次，总标记数 O(n)，故严格线性。 - 预处理素数表：筛一次后，素数表
primes与标记数组isPrime可长期复用——后续「x 是素数吗」O(1) 查询、「第 k 个素数」O(1) 取。 - 最小质因子表 spf：筛法中记录每个数的最小质因子（线性筛天然支持，埃氏筛改造内层即可），用于 O(log n) 质因数分解。
- 质因数分解：基于 spf 反复「除以最小质因子」直到为 1，复杂度 O(log n)（因子个数对数级）。
- 积性函数筛法：欧拉函数 φ、莫比乌斯函数 μ、约数个数等可在线性筛过程中「顺便」算出，利用最小质因子递推。
- 何时用哪种：判单数用试除 O(√n)；
n ≤ 10⁷用埃氏筛（常数小更快）；n极大或需严格线性、需 spf/积性函数时用线性筛。 - 上限参考：
n = 10⁷埃氏/线性均约几十毫秒；n = 10⁸约 0.5~1 秒、内存约 100MB；n ≥ 10⁹需分段筛或位压缩。
一、埃氏筛的常数优化
从 p² 起筛
朴素埃氏筛内层从 2p 开始，但 p 之前每个更小的素因子已经筛过 p 的那些小倍数。具体地，对素数 p，任何倍数 m = k × p（k < p）都含有 k 的某个素因子 p' ≤ k < p，于是 m 在筛 p' 时已标过。所以内层可以从 p² 开始：
for (let k = p * p; k <= n; k += p) // 起点从 2p 优化为 p²
isPrime[k] = false;这一步对大 p 尤其有效（p 越大，省下的「已筛倍数」越多），实测能把埃氏筛提速近一半。注意：p * p 可能溢出 32 位整数，大 n 时用 p <= n / p 作为外层条件、k 用 BigInt 或 Number（JS 安全整数内）。
外层只到 √n 与只筛奇数
- 外层到 √n：当
p > √n时p² > n，内层循环一次都不执行，所以外层条件用p * p <= n即可停。 - 只筛奇数：2 之外素数都是奇数。可单独把 2 的倍数标掉，之后只处理奇数下标（
isPrime[i]对应实际数2i+1），空间减半、内层步长翻倍。
// 只筛奇数的埃氏筛（空间减半）
function sieveOdd(n) {
const isPrime = new Array(Math.floor(n / 2) + 1).fill(true); // 下标 i 对应数 2i+1
for (let i = 1; 2 * i + 1 <= n; ) { /* 略：对奇素数筛奇倍数 */ }
// 单独返回 2 与奇素数
}进一步用 BitSet（位压缩）每个 bit 存一个数的真伪，空间再除 8——n = 10⁹ 时约 125MB，可塞进内存。
分段筛（超大区间）
n 大到数组都开不下（如 n = 10¹¹）时，用分段筛（segmented sieve）：先用普通筛求出 [2, √n] 内的素数，再把 [1, n] 分成长度 B（如 10⁶）的段，每段用 [2, √n] 的素数去筛。空间从 O(n) 降到 O(√n + B)。
二、线性筛为何严格 O(n)
线性筛的正确性已在上一叶说明（break 保证每个合数只被最小质因子筛）。这里再从复杂度角度量化：设合数 m 的最小质因子为 p，则 m 恰在「外层 i = m/p、内层素数 p」那一次被标记。由于「m 的最小质因子」是唯一确定的，这种 (i, p) 组合也唯一——每个合数恰好被访问一次。合数共约 n 个，外层 i 从 2 到 n，故总操作 O(n)，即严格线性。
代价是常数：线性筛每个 i 都要遍历素数表直到 break，相比埃氏筛「素数才进内层」多了判断与表访问。实测 n = 10⁷ 时埃氏筛（从 p² 起筛）约 30ms，线性筛约 60ms——所以「严格 O(n)」并不等于「实际最快」。
三、预处理素数表：O(1) 素性查询
筛法最大的工程价值是一次预处理、多次复用。筛完后得到两个产物：
isPrime[0..n]：布尔数组，isPrime[x]即「x 是素数吗」，O(1) 查询。primes：所有 ≤n 的素数升序列表，primes[k-1]即「第 k 个素数」，O(1) 取。
// 预处理一次，全局复用
const N = 10 ** 7;
const isPrime = eratosthenes(N); // 或 linearSieve
const primes = [];
for (let i = 2; i <= N; i++) if (isPrime[i]) primes.push(i);
// 后续任意查询都是 O(1)
isPrime[998244353]; // true（典型大素数）
primes[0]; // 2，第 1 个素数
primes.length; // π(N)，N 内素数总数（约 N/ln N）适用场景：多次询问「某数是否为素数」「第几个素数」「区间内素数个数」。注意：筛法不能「在线」——必须先知道查询上界 N 一次性筛完；若查询数远超预处理范围，要么扩大 N 重筛，要么对该数用试除法。
四、最小质因子表 spf 与质因数分解
把筛法稍作改造，让它记录每个数的最小质因子（Smallest Prime Factor, spf），就能做 O(log n) 质因数分解。线性筛天然适合（它本来就用最小质因子筛）：
function buildSpf(n) {
const spf = new Array(n + 1).fill(0); // spf[i] = i 的最小质因子
const primes = [];
for (let i = 2; i <= n; i++) {
if (spf[i] === 0) { spf[i] = i; primes.push(i); } // i 是素数，最小质因子是自己
for (const p of primes) {
if (p > spf[i] || p * i > n) break; // p 超过 i 的最小质因子就停
spf[p * i] = p; // p*i 的最小质因子是 p
}
}
return spf;
}
// O(log n) 质因数分解：反复除以最小质因子
function factorize(x, spf) {
const factors = [];
while (x > 1) {
const p = spf[x];
let cnt = 0;
while (x % p === 0) { x /= p; cnt++; }
factors.push([p, cnt]); // [素因子, 指数]
}
return factors; // 如 factorize(60) => [[2,2],[3,1],[5,1]]
}分解 60 = 2² × 3 × 5：spf[60]=2 → 60/2/2=15 → spf[15]=3 → 15/3=5 → spf[5]=5 → 5/5=1，每步除掉最小质因子，共 O(log n) 步（因子个数对数级）。对比朴素试除分解的 O(√n)，这是巨大提升——前提是已用 O(n) 预处理了 spf 表。
同理可在线性筛中顺便计算欧拉函数 φ（
φ[n]= ≤n 且与 n 互素的个数）、莫比乌斯函数 μ 等积性函数，利用「最小质因子」做递推，这是线性筛相对埃氏筛的另一大优势。
五、何时用哪种筛
| 场景 | 首选 | 复杂度 |
|---|---|---|
判定单个数 n 是否为素数 | 试除法 | O(√n) |
求 [1, n] 全部素数，n ≤ 10⁷ | 埃氏筛（从 p² 起筛） | O(n log log n) |
求 [1, n] 全部素数，n 极大或需严格线性 | 线性筛 | O(n) |
| 大量「x 是否素数」查询（上界固定） | 预处理埃氏筛 + isPrime | 预处理 O(n log log n)，查询 O(1) |
| 频繁质因数分解 | 预处理 spf 表 + factorize | 预处理 O(n)，单次分解 O(log n) |
| 需 φ / μ 等积性函数 | 线性筛（顺便递推） | O(n) |
n 超出内存（如 10¹⁰） | 分段筛 | O(n log log n)，空间 O(√n + B) |
口诀：「单判用试除，小批量埃氏，大或严格线性用欧拉，分解上 spf，超大分段筛。」
交互演示
下一步
筛法与 spf 表是数论算法的基础设施。后续可延伸到欧拉函数 / 莫比乌斯函数筛法、乘法逆元与费马小定理、中国剩余定理等数论专题——它们都以「素数表 + 最小质因子」为底层工具。