小甲鱼 发表于 2023-5-23 04:57:06

寻找素数：欧拉筛法（Sieve of Euler）

寻找素数：欧拉筛法（Sieve of Euler）

缘起

欧拉筛法（Sieve of Euler）是一种计算一定范围内所有素数的算法。

它是基于埃拉托斯特尼筛法的一个改进（没听过的鱼油，请先学习 -> 寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes））。

两者的主要区别在于它保证了每个合数只被它的最小质因数筛去，从而减少了重复操作，提高了筛选效率。

这个筛法的名字来源于著名的数学家欧拉，但并不是由欧拉本人提出的。

它是近年来计算机时代的产物，是一种更适合于计算机运算的筛法。


步骤

下面，小甲鱼给大家阐述欧拉筛法的步骤：

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

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

3. 不同于埃拉托斯特尼筛法，欧拉筛法在筛选合数时，每个合数只会被它的最小质因数筛去。这是通过在内部循环中增加一个判断实现的：如果当前数 i 能被素数整除，就跳出循环。

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

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

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

这种方法的主要优点是效率高，因为每个合数只被筛去一次，而述埃拉托斯特尼筛法每个合数将被筛选若干次。


演示

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

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

zhangjinxuan 发表于 2023-5-23 07:21:10

6666

开心老六 发表于 2023-5-23 10:33:15

讲得不错{:10_254:}

asd11111 发表于 2023-5-24 08:58:32

赞👍

蓝屏爱好者 发表于 2023-5-24 10:20:49

看看

bluepink 发表于 2023-5-24 15:48:08

欧拉筛法（Sieve of Euler）

爱吃梨的猩猩 发表于 2023-5-26 15:37:31

看完看完看完了就知道差距了

zhuyanan 发表于 2023-5-26 15:38:44

真是太厉害了！还可以这么筛选，减少计算机运算量

clollipops 发表于 2023-5-26 15:44:42

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

寻找素数：欧拉筛法（Sieve of Euler）

shane9611 发表于 2023-5-26 15:44:51

赞，欧拉筛法确实提升了效率

面对巨人 发表于 2023-5-26 18:46:17

这样可简便多了

Eric_1891574 发表于 2023-5-26 18:46:33

可以在 3.11 里运行正常吗？

lonely_xiaoying 发表于 2023-5-26 18:47:39

太厉害了这玩意

鸡你实在太没 发表于 2023-5-26 19:01:48

太厉害了这玩意

Tiamsy 发表于 2023-5-26 19:10:00

厉害{:10_275:}

xyt210819 发表于 2023-5-27 17:02:07

讲的不错，还是听不懂

额外减小 发表于 2023-5-28 16:25:31

线性筛（喜）

欧拉计划 发表于 2023-5-29 19:08:48

{:10_254:}

hornwong 发表于 2023-5-30 00:04:16

看看

Axiujiu 发表于 2023-6-3 13:52:02

可否做一期：PageRank算法，这样的呢{:5_102:}
页: [1] 2
查看完整版本: 寻找素数：欧拉筛法（Sieve of Euler）