当前范围 N
100
埃拉托斯特尼（Eratosthenes，约公元前 276 — 前 194）生于昔兰尼（今利比亚境内），约公元前 245 年前后到亚历山大，后来做了亚历山大图书馆的馆长，还做过托勒密三世之子的老师。他一生横跨数学、天文、地理、年代学与诗学；晚年失明，据说绝食而终。
他最有名的功业是量地球：夏至正午，赛伊尼（今阿斯旺）的深井井底不见日影，而同一时刻亚历山大的日影偏离铅垂约 1/50 圆周（约 7°12′）。既然两地近乎在同一子午线上，地球周长就约是两地距离的 50 倍——他给出的结果是 250 000 斯塔德。此外他还测过黄赤交角、编过星表，并主张每四年置一闰日。
筛法的希腊语名字是 κόσκινον Ἐρατοσθένους——「埃拉托斯特尼的筛子」。他的原著已经失传，这把筛子是由尼科马霍斯（Nicomachus，约公元 60–120）在《算术引论》里记载下来的。
它是怎么做的？先把 1 到 N 按顺序写下来；第一步划掉 1（它既不是质数也不是合数）；此后第一个没被划掉的数是 2，把它留下，然后把从它往后每一个第 2 个数都划掉；再下一个没被划掉的数是 3，留下它，划掉此后每一个第 3 个数……有些数会被划掉不止一次（例如 6、12），因为它们同时是 2 和 3 的倍数。当第一个没被划掉的数超过 √N 时就可以收手了——此时留下的数，全都是不超过 N 的质数。
比筛法更早的一条结论，是质数有无穷多个：欧几里得《几何原本》第九卷命题 20 用反证法说明——若质数只有 p₁…pₙ 这有限个，那么 p₁p₂…pₙ + 1 除以其中任何一个都余 1，它既不能被这些质数整除，就必然含有新的质因子，矛盾。所以「筛」永远筛不完，质数也永远筛不尽。
需要说明的是，质数理论源自古希腊；《九章算术》长于算法与应用（方田、粟米、衰分、商功、均输、盈不足、方程、勾股），并没有质数专题——这也是数学在不同文明里各走一路的例证。
这把两千多年前的「手工筛」，直到电子计算机出现之前，一直是找质数的主要办法；在计算机时代，它演化出位筛、分段筛、线性筛，至今仍是数论与密码学里筛掉大批合数的第一道工序。
| 年代 | 事件 |
|---|---|
| 约前 276 | 生于昔兰尼（今利比亚） |
| 约前 245 | 赴亚历山大，后任亚历山大图书馆馆长 |
| 约前 240 | 以日影法测出地球周长约 250 000 斯塔德 |
| — | 测黄赤交角、编星表、主张四年一闰 |
| 约前 194 | 卒于亚历山大 |
| 后世 | 筛法经尼科马霍斯《算术引论》记载而传世 |
① 写下 2 到 N 的全部整数（本工坊把 1 的位置留空：1 既不是质数也不是合数）。
② 取最小的未被划去的数 p，它就是下一个质数，圈出来。
③ 划去 p 的所有倍数：2p、3p、4p……（p 自己留下）。
④ 重复 ②③，直到某个未划去的数 p 满足 p² > N。
⑤ 剩下的数全部是质数——筛完。
设 n ≤ N 是合数，则 n = a·b 且 1 < a ≤ b < n，于是 a ≤ √n ≤ √N。把 a 再分解成质数之积，就得到 a 的某个质因子 q ≤ √N，且 q 整除 n。也就是说：任何合数都有一个不超过 √N 的质因子，它一定会在某一轮里被划掉。反之，若某个数在全部「≤ √N 的质数」轮次结束后仍未被划去，它就不可能是合数——只能是质数。
所以 N = 100 只需筛 2、3、5、7 四次（因为 11² = 121 > 100）；N = 200 需要筛 2、3、5、7、11、13 六次（17² = 289 > 200）。这正是页面上「筛的次数」的来历。
朴素筛的划去次数是 Σp ≤ √N N/p ≈ N·ln ln N，即 O(N log log N)（Mertens 定理），几乎只比「读一遍数」贵一点，是极快的经典算法。常见优化：
① 从 p² 起划：2p、3p、…、(p−1)p 已经被更小的质数划过了，没必要重复。
② 只存奇数或用位筛（每个数只占 1 位），内存省到 1/64。
③ 分段筛：不一次开 N 个格子，按段处理，大 N 也能跑。
④ 线性筛（欧拉筛）：保证每个合数只被它的最小质因子标记一次，做到 O(N)。
请注意：本工坊的演示页故意从 2p 起划（不做第 ① 条优化），这样才会出现「已经划掉的数又被划到」的现象——那正是您在页面上看到的闪现三次的提醒。第 ① 条优化之后，这种重复几乎就没有了（只剩 p² 与更小质数倍数重叠的少数情形）。
| N | π(N) 质数个数 | 筛的次数 | 划去（首次） | 闪现提醒 | 总步骤 |
|---|
注：「划去（首次）」是把每个合数第一次划掉的次数；「闪现提醒」是后续轮次再遇到它时的次数。两者相加就是全部划去动作。总步骤 = 圈出质数 + 划去 + 闪现 + 每轮收束 + 收尾。
要用 RSA 这类公钥密码，就得先找到很大的质数（几百位）。做法是：先随机取一个大奇数，用小质数筛把能一眼除尽的候选全排掉（这一步正是埃拉托斯特尼筛法的思路），再用 Miller–Rabin 等素性检验确认。也就是说，两千多年前的这把筛子，今天依然在密码学的第一道工序上工作。
质数到底有多密？质数定理说 π(x) 约等于 x / ln x（高斯、勒让德早年猜想，1896 年由 Hadamard 与 de la Vallée Poussin 证明）。它不是精确公式：π(1000) = 168，而 1000 / ln 1000 ≈ 145——「约」字很要紧，这也正是数论后来两百年的主战场。