type
status
date
slug
summary
tags
category
icon
password
埃拉托斯特尼筛法是一种由古希腊数学家埃拉托斯特尼提出的一种简单检定素数的算法。它的原理是从2开始，将每个素数的各个倍数标记成合数，最后剩下的未被标记的数就是素数。
例如，要得到自然数25以内的全部素数，可以按照以下步骤进行：
- 列出2以后所有数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 标记第一个素数2：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 用红色标记2的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 如果最大数不大于最后一个标出的素数的平方，那么剩下的所有的数都是素数，否则回到第二步。本例中，25大于2的平方，返回第二步。
- 剩下的序列中第一个素数是3，用蓝色标记3的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 得到的素数是2，3。
- 25仍然大于3的平方，再次返回第二步。
- 序列中第一个素数是5，用绿色标记5的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 得到的素数是2，3，5。
- 因为25是5的平方，筛选完毕。
- 结论：去掉红色、蓝色和绿色的数，25内的素数是2，3，5，7，11，13，17，19，23。
- Author:SnowDreamXUE
- URL:https://notion.snowdreamxue.top/article/1f4e0b82-56dc-8046-bad5-e03d3e4f3580
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts
