知识/定理
筛法：列出 $2$ 至 $N$ 的整数，从 $2$ 起逐个划去其倍数，剩下的即素数。
公式
素数集合 $\{p\le N : p\ \text{不被更小素数整除}\}$；算法复杂度 $O(n\log\log n)$。
证明思路
每个合数 $n$ 有素因子 $\le\sqrt{n}$，故划到 $\sqrt{N}$ 即止。
应用/例子
素数表的基本算法；同人用夏至正午两城日影差测地球周长，误差 <5%。
意义/影响
数论与计算的基本工具；演示了数学方法在实测中的应用。
DOXA · 数学编年史 · 知识详情
约前240 ｜ 埃拉托色尼 ｜ 代数·数论 ｜ 方法
筛法：列出 $2$ 至 $N$ 的整数，从 $2$ 起逐个划去其倍数，剩下的即素数。
素数集合 $\{p\le N : p\ \text{不被更小素数整除}\}$；算法复杂度 $O(n\log\log n)$。
每个合数 $n$ 有素因子 $\le\sqrt{n}$，故划到 $\sqrt{N}$ 即止。
素数表的基本算法；同人用夏至正午两城日影差测地球周长，误差 <5%。
数论与计算的基本工具；演示了数学方法在实测中的应用。