1) 朴素筛（试除式标记 / 对每个数枚举倍数）

形式

对每个 $i=2..n$，把 $2i,3i,4i,\dots\le n$ 标记。

复杂度：$\displaystyle O(n\log n)$

证明：
总标记次数 $ T=\sum_{i=2}^{n}\left\lfloor\frac{n}{i}\right\rfloor-1 = \Theta\!\left(\sum_{i=2}^{n}\frac{n}{i}\right) = n\cdot \Theta\!\left(\sum_{i=2}^{n}\frac{1}{i}\right) $ 而调和级数 $\sum_{i=2}^{n}\frac{1}{i} = \Theta(\log n)$ 所以 $T=\Theta(n\log n)$，即时间 $O(n\log n)$。

这也是“对所有 i 枚举倍数”的典型复杂度模板。

2) 埃氏筛（只用质数去划掉倍数）

形式

对每个质数 $p\le n$，标记 $2p,3p,\dots$（经典优化从 $p^2$ 开始，但对主项影响不大）。

复杂度：$\displaystyle O(n\log\log n)$

证明核心： 总标记次数近似 $ T \approx \sum_{p\le n}\frac{n}{p}=n\sum_{p\le n}\frac{1}{p} $ 关键是著名结论（梅滕斯/Mertens 型结论）： $\sum_{p\le n}\frac{1}{p} = \log\log n + O(1)$ 于是 $T = n(\log\log n + O(1)) = O(n\log\log n)$

补充说明（为啥从 $p^2$ 开始不改变主项）：
如果从 $2p$ 开始 vs 从 $p^2$ 开始，少标记的项数大约是 $ \sum_{p\le \sqrt n} O(p) = O\!\left(\sum_{p\le \sqrt n} p\right) $ 它远小于 $n\log\log n$ 的主项（实际上是低阶项），所以总体仍是 $O(n\log\log n)$。

竞赛里通常直接把埃氏筛记为 $O(n\log\log n)$，这是“只按质数枚举倍数”的经典结果。

3) 线性筛（欧拉筛，Linear Sieve）

形式

维护质数表 pr[]。对每个 $i=2..n$：
枚举质数 $p$（从小到大），令 $x=i\cdot p\le n$ 则标记 $x$。
一旦 $p\mid i$ 就 break。

复杂度：$\displaystyle O(n)$

证明（唯一生成/唯一标记思想）：

在线性筛里，每个合数 $x$ 会且只会在 唯一的一次 被标记：
设 $p=\operatorname{lp}(x)$ 是 $x$ 的最小质因子，令 $i=x/p$。
当算法处理到这个 $i$ 时，会遍历到 $p$，生成 $i\cdot p=x$。

还要证明不会被别的 $(i',p')$ 再次生成：
如果 $x=i'p'$ 且 $p'$ 是枚举到的质数，那么线性筛的 break 规则保证：
一旦 $p'\mid i'$ 就停，而能生成 $x$ 的那次必须满足 $p'\le \operatorname{lp}(i')$。
若 $p'>\operatorname{lp}(x)$，则 $p'$ 不可能成为“第一次生成” $x$ 的质数；
若 $p'=\operatorname{lp}(x)$，则对应 $i'=x/p'$ 就是上面的唯一那一个。

因此：每个合数被标记恰好一次。标记次数 $\le n$，再加上遍历 $i$ 的外层 $n$ 次，整体 $O(n)$。

这也是线性筛最重要的性质：把“埃氏筛里一个合数会被多次划掉”变成“恰好一次”。

4) 最小质因子筛 / SPF（常见于分解与欧拉函数等预处理）

如果你用线性筛顺便维护 lp[i]（最小质因子），那么：

• 预处理：$O(n)$（同线性筛证明）
• 单次分解一个数 $x$：每次除以 lp[x]，次数等于质因子个数（含重），为 $O(\log x)$ 上界（因为每次至少除以 2）。
• 分解所有 $1..n$ 不是线性的（会更大），但竞赛一般是“预处理一次 + 分解若干查询”。

5) 分段筛（Segmented Sieve）

任务

求区间 $[L,R]$ 内所有质数，$R$ 可很大，但区间长度 $m=R-L+1$ 相对可控。

复杂度：$\displaystyle O\big(m\log\log R + \sqrt R\big)$（常见写法）

证明要点：

1. 先筛出 $\le \sqrt R$ 的所有质数：用埃氏筛，耗时 $O(\sqrt R\log\log \sqrt R)$ = $O(\sqrt R\log\log R)$。常写成 $O(\sqrt R)$ 级别的预处理项（主项看实现/数据）。
2. 对每个质数 $p\le \sqrt R$，在区间里划掉它的倍数，次数约为 $m/p$。
   总次数 $ T \approx \sum_{p\le \sqrt R}\frac{m}{p}=m\sum_{p\le \sqrt R}\frac{1}{p} = m(\log\log \sqrt R + O(1)) = O(m\log\log R) $ 合起来就是 $O(m\log\log R + \sqrt R\log\log R)$，常写成 $O(m\log\log R+\sqrt R)$。

要点总结表格

筛法	典型做法	时间复杂度	关键原因
朴素枚举倍数	对每个 $i$ 标记 $ki$	$O(n\log n)$	调和级数 $\sum 1/i$
埃氏筛	只对质数 $p$ 标记倍数	$O(n\log\log n)$	$\sum_{p\le n} 1/p = \log\log n + O(1)$
线性筛（欧拉）	`p	i` 时 break，合数只标一次	$O(n)$	每个合数唯一由最小质因子生成
分段筛	区间长度 $m$，用 $\le\sqrt R$ 质数划掉	$O(m\log\log R+\sqrt R)$	区间内标记次数 $\sum m/p$