素数筛（埃氏筛 / 线性筛）
素数（Prime）是大于 1、只能被 1 和自身整除的自然数，是数论的「原子」——任何大于 1 的整数都能唯一分解成素数的乘积（算术基本定理）。当问题从「判定单个数是否为素数」升级到「求区间 [1, n] 内所有素数」时，逐个用试除法判定会达到 O(n√n)，显然不可接受。素数筛（Prime Sieve） 正是批量求素数的利器：它用一个布尔数组标记「谁是合数」，让每个素数去「筛掉」自己的倍数。
素数筛的核心矛盾是「一个合数会被多次筛到」。埃拉托斯特尼筛（Sieve of Eratosthenes） 思路最直观：对每个素数 p，把它所有的倍数 2p、3p、... 标记为合数，复杂度 O(n log log n)（接近线性，但 12 会被 2 和 3 各筛一次，存在重复）。线性筛 / 欧拉筛（Linear Sieve） 通过「每个合数只被它的最小质因子筛掉一次」这一约束，把复杂度压到严格的 O(n)——代价是需要额外维护一张「已知素数表」并配合一个提前 break。掌握这两种筛法，再加上用筛法预处理的「最小质因子表（spf）」做 O(log n) 质因数分解，就覆盖了竞赛与面试中绝大多数素数相关问题。
评价
优点
- 批量高效：求
[1, n]全体素数，埃氏筛 O(n log log n)、线性筛 O(n)，远优于逐个试除的 O(n√n) - 思路直观：埃氏筛「素数 p 筛掉 p 的倍数」一句话讲清，实现仅需一个布尔数组与一层循环
- 可扩展：筛法过程天然产出「素数表」「最小质因子表（spf）」，支持 O(1) 素性查询与 O(log n) 质因数分解
- 常数小、缓存友好：连续的布尔数组顺序访问命中缓存，实际速度常优于理论复杂度
缺点
- 空间 O(n)：必须开
n+1的标记数组，n 很大（如 10⁹）时内存吃不消——超大区间需用「分段筛」 - 不能在线：筛法是一次性预处理，适合「先建表、多次查询」；若只判一个数，试除法更划算
- 线性筛常数偏大：虽有更优的 O(n) 渐近，但额外的素数表与
break判断使常数大于埃氏筛，小数据下埃氏筛往往更快
本叶地图
- 入门 —— 素数定义、试除法判定 O(√n)、为什么需要筛法、埃氏筛与线性筛两种思路总览
- 埃氏筛与线性筛：两种筛法详解 —— 埃氏筛标记倍数 O(n log log n)、重复筛问题、线性筛最小质因子筛一次 O(n)、完整代码
- 优化与应用场景 —— 从 p² 开始筛、预处理素数表、用 spf 做质因数分解、何时用哪种筛
- 参考 —— 复杂度表、试除/埃氏/线性代码模板、应用清单、易错点