寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes）

小甲鱼 · 发表于 2023-5-23 03:28:33

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes）

缘起

关于素数（质数）的寻找，可以追溯到古希腊时期（大约在公元前 300 年左右）。

这是人类历史上首次明确提出并研究素数的时期。

希腊数学家欧几里得在他的著作《几何原本》中证明了素数是无穷的，这是关于素数的最早的已知理论结果。

埃拉托斯特尼同样是一位古希腊数学家，今天我们要讲的就是他发明的一种用来寻找一定范围内所有素数的算法 —— 埃拉托斯特尼筛法 (Sieve of Eratosthenes)。

埃拉托斯特尼（Eratosthenes）生活在公元前 276 年 ~ 公元前 194 年，是一位古希腊的数学家、地理学家、诗人、天文学家和音乐家。

他是亚历山大图书馆的主管，也是古代世界最重要的学术中心之一。

埃拉托斯特尼是第一个计算出地球周长的人，他的计算结果与现代测量结果非常接近。

步骤

下面，小甲鱼给大家阐述埃拉托斯特尼筛法的步骤：

1. 创建一个列表，表示每个数字是否是素数。初始化时，我们先假设所有的数都是素数（除了 0 和 1，地球人都知道它们不是素数）。

2. 从最小的素数 2 开始，如果一个数是素数，就把它的所有倍数标记为非素数。这一步被称为 “筛选”，因为我们在筛选出所有由当前素数产生的合数。

3. 找到下一个仍被标记为素数的数字，然后把它的所有倍数标记为非素数。

4. 重复第 3 个步骤，直到所有的数都被处理过。

5. 最后，仍被标记为素数的数字就是所有的素数。

演示

如果无法播放，请点击此处在新窗口打开

实现

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan · 发表于 2023-5-23 07:19:50

6666

yinda_peng · 发表于 2023-5-23 18:20:00

这学期期末结束就开始系统性学习算法

bluepink · 发表于 2023-5-24 15:51:03

爱吃梨的猩猩 · 发表于 2023-5-24 19:35:52

开始认真学习中加油加油

clollipops · 发表于 2023-5-24 19:36:15

本帖最后由 clollipops 于 2023-7-25 18:33 编辑

寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes）

鸡你实在太没 · 发表于 2023-5-24 19:41:12

这学期期末结束就开始系统性学习算法

lonely_xiaoying · 发表于 2023-5-24 19:51:59

虽然看不懂但是感觉好厉害

xyt210819 · 发表于 2023-5-24 20:02:15

有点看不懂，还是要不断学习，好好学习python，加油

Eric_1891574 · 发表于 2023-5-24 20:52:19

原理是明白了，在学 delphi 老师能不能帮忙谢一个 delphi 的代码呢？

shane9611 · 发表于 2023-5-24 22:52:53

学到了～

zhuyanan · 发表于 2023-5-24 23:17:36

又回去把素数复习了一遍素数就是质数

Tiamsy · 发表于 2023-5-25 15:41:04

加油！

凌凌祺 · 发表于 2023-5-26 11:53:42

5月26加油，月底！

欧拉计划 · 发表于 2023-5-29 04:20:54

支持！

鱼小二 · 发表于 2023-6-16 23:43:18

小绿c · 发表于 2023-6-17 00:03:58

setr5h

xyLi · 发表于 2023-6-27 15:35:55

Mr.roushan · 发表于 2023-7-5 11:55:17

看看思路

songyazh · 发表于 2023-7-8 13:09:54

支持

账号		自动登录	找回密码
密码			立即注册

[技术交流] 寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes）

马上注册，结交更多好友，享用更多功能^_^

评分

本帖被以下淘专辑推荐:

浏览过的版块