概念

埃拉托斯特尼筛

逐个划去合数留下素数的古老算法，复杂度接近线性，是筛法的原型。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

埃拉托斯特尼筛解析数论

01定义

从 2 起逐个标记素数、划去其倍数，留下的即素数——两千三百岁的算法至今仍是生成素数表的工业标准，复杂度近似线性，也是「筛法」一切现代变体的原型。

经典筛：小素数层层过滤，合数落网

只筛到 $\sqrt{n}$ （合数必有小素因子），总操作 $\sum_{p\leq\sqrt{n}}\frac{n}{p}=O(n\log\log n)$ ；线性筛（欧拉筛）进一步做到每个合数恰被标记一次。

把「划去倍数」抽象为容斥原理：估计与一组素数互素的整数个数——现代筛法用权重优化把容斥截断误差控制住。

位图压缩（只存奇数）、分段筛（缓存友好）、轮式分解（跳过 2、3、5 的倍数）——数论软件与素数纪录的基础设施。

\pi(n)\approx n\prod_{p\leq\sqrt{n}}\Big(1-\frac{1}{p}\Big),\quad\text{筛的启发式}

埃拉托斯特尼（约公元前 240 年）发明；欧拉给出乘积形式的分析；现代计算机时代经分段与位压缩优化，仍是 GIMPS 等素数搜索项目的预处理标准。

密码学的素数表预生成、整数分解的试除阶段、哥德巴赫猜想的数值验证（已验证至 $4\times 10^{18}$ ）、数学教育与素数可视化。

筛法网格：逐步划去合数依次用 2、3、5、7 划去倍数：幸存者是素数，删除线是合数

n 筛选上限50k 已用质数个数1