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

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

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

缘起

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

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

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

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

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

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

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

步骤

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

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

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

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

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

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


演示

https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/Algorithm/SieveOfEratosthenes.mp4

实现
**** Hidden Message *****

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

6666

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

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

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

{:5_102:}

爱吃梨的猩猩 发表于 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

{:7_146:}

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

setr5h

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

666

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

看看思路

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

支持
页: [1] 2
查看完整版本: 寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes）