鱼C论坛

 找回密码
 立即注册
查看: 1571|回复: 35

[技术交流] 寻找素数:欧拉筛法(Sieve of Euler)

[复制链接]
发表于 2023-5-23 04:57:06 | 显示全部楼层 |阅读模式

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

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

x
寻找素数:欧拉筛法(Sieve of Euler)


缘起

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

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

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

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

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


步骤

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

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

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

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

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

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

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

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


演示



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


评分

参与人数 1鱼币 +2 收起 理由
zhangjinxuan + 2 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-5-23 07:21:10 From FishC Mobile | 显示全部楼层
6666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-5-23 10:33:15 | 显示全部楼层
讲得不错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-24 08:58:32 | 显示全部楼层
赞👍
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-24 10:20:49 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-5-24 15:48:08 | 显示全部楼层
欧拉筛法(Sieve of Euler)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 15:37:31 From FishC Mobile | 显示全部楼层
看完看完看完了就知道差距了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 15:38:44 From FishC Mobile | 显示全部楼层
真是太厉害了!还可以这么筛选,减少计算机运算量
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 15:44:42 From FishC Mobile | 显示全部楼层
本帖最后由 clollipops 于 2023-7-25 18:34 编辑

寻找素数:欧拉筛法(Sieve of Euler)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 15:44:51 From FishC Mobile | 显示全部楼层
赞,欧拉筛法确实提升了效率
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 18:46:17 | 显示全部楼层
这样可简便多了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 18:46:33 From FishC Mobile | 显示全部楼层
可以在 3.11 里运行正常吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 18:47:39 From FishC Mobile | 显示全部楼层
太厉害了这玩意
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 19:01:48 From FishC Mobile | 显示全部楼层
太厉害了这玩意
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-26 19:10:00 | 显示全部楼层
厉害
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-5-27 17:02:07 From FishC Mobile | 显示全部楼层
讲的不错,还是听不懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-28 16:25:31 | 显示全部楼层
线性筛(喜)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-29 19:08:48 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-5-30 00:04:16 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-6-3 13:52:02 | 显示全部楼层
可否做一期:PageRank算法,这样的呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 18:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表