关于埃拉托斯特尼筛法 - 素数筛的原理

埃拉托斯特尼大约生活在公元前 276 年到公元前 194 年，曾主持亚历山大大图书馆。他最著名的成就是根据两座城市里影子的长度测量了地球的大小。这种筛法以他命名，是因为格拉森的尼科马库斯在约公元 100 年写成的《算术入门》中把它描述为埃拉托斯特尼的方法。

写下从 2 到 N 的数。第一个数 2 是素数：划掉 4、6、8 以及 2 的其他所有倍数。剩下的下一个数 3 是素数：划掉 9、12、15 等等。继续处理 5、7 以及之后剩下的数。一个从未被划掉的数没有更小的因数，所以它是素数。

N 以内的每个合数都有一个不大于 N 的平方根的素因数。所以一旦 p² 大于 N，就没有什么可划的了。要找出 100 以内的素数，只需要 2、3、5 和 7；找 1000 以内的素数，只需要 31 以内的素数。

筛法大约需要 N log log N 步，只比 N 本身增长得稍快一点。计算机至今仍在使用它，通常分段进行，称为分段筛，用来列出数十亿以内的素数。若要判断单个大数是否为素数，其他方法更快。

常见问题

埃拉托斯特尼筛法是谁发明的？

它以公元前三世纪的希腊学者昔兰尼的埃拉托斯特尼命名。现存最早的文字描述来自约公元 100 年的格拉森的尼科马库斯。

为什么筛法从 p² 开始划？

p 的每个较小倍数都有一个更小的素因数，所以更小的素数已经把它划掉了。

1000 以下有多少个素数？

1000 以下有 168 个素数，最大的是 997。

在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。