虫儿飞飞
如何利用埃拉托斯特尼筛法找出1000以内的所有质数？
如何利用埃拉托斯特尼筛法找出1000以内的所有质数呢？是不是觉得听起来有点抽象，其实只要跟着步骤走，很快就能掌握？
作为历史上今天的读者（www.todayonhistory.com），我一直觉得数学里的很多古老方法都充满智慧，埃拉托斯特尼筛法就是其中之一。它诞生于两千多年前，却至今仍被广泛使用，这种跨越时空的实用性，本身就很让人着迷。
什么是埃拉托斯特尼筛法？
埃拉托斯特尼筛法是古希腊数学家埃拉托斯特尼发明的一种寻找质数的方法。质数，就是那些大于1、除了1和自身外不能被其他数整除的自然数，比如2、3、5、7等。
这种方法的核心思路很简单：像用筛子筛东西一样，把不是质数的数（也就是合数）一个个“筛掉”，剩下的就是质数。为什么叫“筛法”？因为它就像农民筛粮食，把杂质去掉，留下饱满的颗粒，这里的“杂质”就是合数，“颗粒”就是质数。
用埃拉托斯特尼筛法找1000以内质数的具体步骤
要找出1000以内的质数，按照以下步骤操作即可：
-
列出数字范围：先把1到1000的所有自然数按顺序写出来（或者在表格里排列）。这里要注意，1不是质数也不是合数，一开始就可以标记出来。
-
从最小的质数开始“筛”：
- 找到第一个未被标记的数，这个数就是质数，它是2。
-
把2后面所有2的倍数（4、6、8、10……998、1000）都标记为合数，因为它们能被2整除，不是质数。
-
继续筛选下一个质数：
- 接着找下一个未被标记的数，是3。
-
把3后面所有3的倍数（6、9、12、15……999）标记为合数，注意已经被2标记过的数（比如6）不用重复标记。
-
重复操作直到结束：
- 下一个未被标记的数是5，标记所有5的倍数（10、15、20……1000）。
- 以此类推，直到筛选到的质数的平方大于1000为止。为什么？因为如果一个数n≤1000是合数，它一定有一个不大于√1000（约31.6）的质因数，所以筛到31就够了。
用表格直观展示筛选过程（以1-30为例）
| 数字 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |------|---|---|---|---|---|---|---|---|---|----| | 标记情况 | 非质数 | 质数 | 质数 | 2的倍数（合数） | 质数 | 2和3的倍数（合数） | 质数 | 2的倍数（合数） | 3的倍数（合数） | 2和5的倍数（合数） | | 数字 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |------|----|----|----|----|----|----|----|----|----|----| | 标记情况 | 质数 | 2和3的倍数（合数） | 质数 | 2和7的倍数（合数） | 3和5的倍数（合数） | 2的倍数（合数） | 质数 | 2和3的倍数（合数） | 质数 | 2和5的倍数（合数） | | 数字 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | |------|----|----|----|----|----|----|----|----|----|----| | 标记情况 | 3和7的倍数（合数） | 2和11的倍数（合数） | 质数 | 2和3的倍数（合数） | 5的倍数（合数） | 2和13的倍数（合数） | 3的倍数（合数） | 2和7的倍数（合数） | 质数 | 2、3、5的倍数（合数） |
从表格里能清楚看到，1-30中的质数有：2、3、5、7、11、13、17、19、23、29，共10个。按照同样的逻辑扩大到1000，就能找出所有质数了。
筛选时容易踩的“坑”
- 漏看数字范围：有人会忘记1不是质数，把1也算进去，这是最常见的错误。记住，质数的定义是“大于1的自然数”，所以1一开始就要排除。
- 重复标记浪费时间：比如6既是2的倍数也是3的倍数，第一次被2标记后，遇到3时就不用再管它了，不然会做无用功。
- 停止筛选的时机不对：有人会一直筛到1000才停，其实只要筛到31就够了（因为312=961，372=1369＞1000），超过31的质数，它们的倍数在之前的步骤里已经被筛掉了。
这种方法在生活中的小应用
可能有人会问，现在有计算器和电脑，为什么还要学这种手动筛法？其实，理解筛法的原理能帮我们更好地掌握质数的特性。比如在设置密码时，很多加密算法会用到大质数，了解质数的筛选逻辑，就能明白为什么大质数更难被破解。
作为历史爱好者，我觉得埃拉托斯特尼的智慧特别值得称道。两千多年前没有计算机，他却能想出如此高效的筛选方法，这种化繁为简的思维，至今仍在影响着数学和科技领域。据统计，1000以内的质数共有168个，如果你按筛法一步步操作，最后得到的数量一定是这个数，不妨亲自试试验证一下~