前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|欧拉筛法求质数

Python|欧拉筛法求质数

作者头像
算法与编程之美
发布2020-09-24 10:48:48
1.6K0
发布2020-09-24 10:48:48
举报
文章被收录于专栏:算法与编程之美

问题描述

我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……请你计算第 2020 个质数是多少?

解决方案

当看到这种寻找质数的问题,很多人第一时间想到的便是二重循环暴力查找,如果只找前几个质数,可以使用这种暴力查找的方法。但如果要找第2020个质数,第9999个质数,这种暴力方法就不适用了。

这个时候就可以使用筛法来求质数,本文介绍的是欧拉筛法。其运用的原理是质数的倍数一定不是质数。因此将质数的倍数直接标记成合数,以达到筛选质数的目的。

同样以此为思路的还有埃氏筛法,但埃氏筛法具有缺陷:对于一个合数,有可能被筛多次,例如20 = 2*10 = 4*5。而对此进行改进,用合数的最小质因子进行筛选来确保每个合数只被筛选一次,这就是欧拉筛法。

但是具体是怎么做到每个合数只被筛选一次,我们来看下面的代码。

代码:

def ouLaShai(n): lis = [True for i in range(n + 1)] # 用于筛选记录合数 lis2 = [] # 存质数 for i in range(2, n + 1): if lis[i]: # 如果没有被筛选就加到Lis2 lis2.append(i) for prime in lis2: if i * prime > n: # 保证小于n,不能超出范围 break lis[i * prime] = False # 记录合数 if i % prime == 0: # 关键步骤,确保每个合数只被筛选一次 break return lis2

这些代码中有一个非常关键,也是确保每个合数只被筛选一次的代码:

if i % prime == 0: break

当i % prime == 0时,prime就是i的质因子,就有i = x(某个数) * prime。而到后面的某个质数prime2去筛i * prime2的时候,就有i * prime2 == x * prime * prime2,因而prime和prime2都是i * prime2的质因子。但由于prime< prime2,i * prime2的最小质因数就是prime而不是prime2。所以为了避免合数被重复筛选,当i % prime == 0时,就直接break。

例如:i=2筛选4,i=3筛选6和9,但到i=4的时候,prime先为2,筛掉8,但运行到I % prime == 0这一步的时候就直接break了,也就避免了再遍历prime = 3的时候筛掉12,而12是由i = 6时,prime = 2时筛掉。

能力越强,责任越大。

实事求是,严谨细致。

【where2go团队出品】

END

实习主编 | 王文星

责 编 | 雀 跃

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档