素数筛选算法

全文概要

最近学习了一种筛素数的方法,能够以时间复杂度O(n),即线性时间完成。一开始不能理解其中的一句话,搜索了很久,大部分结果都是一群人在网上卖萌。好好思索了一番,按照自己的思路终于理解了。本文的内容绝不卖萌,但也难称严谨,仅以备忘,欢迎斧正。

暴力法


没接触这种方法之前,如果面试官让我筛一下素数,即给定上限 $n$,找出从 $1$ 到 $n$ 之间所有的素数/质数) 我大概率会说:(作谦虚状)好的,我尽力试一试。 其实心里暗喜:嗯,很轻松嘛,然后不假思索写下…

就像这样:

1234567891011

void PrintPrimer(int n){ for(int i = 2; i <= n; i++) { for(int j = 2; j < i; j++) if(i % j == 0) break; if(j == i) cout << i << endl; }}

正准备提交时,突然听到对面一声叹息…不经意望去,对方面露鄙夷,心觉不妙… 再看看自己刚写的代码,我的天!遍历???还可以更low一点吗…估计此时面试官和我都想问同一个问题:你到底有没有学过算法?

于是两秒钟的自我检讨之后,赶紧改了上面代码的几个判断条件,成了这样:

1234567891011

void PrintPrimer(int n){ for(int i = 3; i <= n; i += 2) { for(int j = 3; j <= sqrt(i); j += 2) if(i % j == 0) break; if(j * j > i) cout << i << endl; }}

嗯…至少不用遍历,对每个数只用检查到其平方根,另外还可以要判断的数从3开始每次加2可以跳过全部偶数,因为偶数肯定不是素数啦,运算次数是降低了不少,可复杂度不还是 $O(n^2)$ 吗?

不对…对面那家伙脸色不太好,好像更加不耐烦了…怎么办,不慌不慌…

筛法


于是,我再度埋下头,看起来像是在认真思考,其实只是不敢直视对方…

哎,慢着!灵机一闪,思绪回到了大二算法课上,老师讲过一种叫做“筛法”的东东,不过好像记不太清了,我再想想…

半分钟后…

回来了,我感到它们全都回来了!

拍拍脑袋后奋笔疾书,筛法跃然纸上:

1234567891011121314151617181920

void PrintPrimer(int n){ bool is_primer[n]; // 标志位数组,记录下标对应数字是否被筛除掉 memset(is_primer, true, n); for(int i = 2; i <= n; i++) { if(is_primer[i]) { for(int j = 2 * i; j <= n; j += i) is_primer[j] = false; // 访问到一个素数时,就将其倍数都标记为非素数 } } for(int i = 2; i <= n; i++) { if(is_primer[i]) cout << i << endl; }}

这会儿人自信多了,压箱底的老本被翻了出来,总不能有差了,直勾勾地望向面试官,只见他面色稍宽,眉宇间仍透露着几分不满,说道:我看你换了几种算法了,前面的就不说了,给你一个大数据的场景,比如1~1000000的范围,输出其中的素数,你这种筛法的时间性能还能看嘛?

嗯…毫不留情,莫非还有更优的算法?

“您容我再想想哈~”,陪着笑脸说完,双手抱头痛苦思考状/(ㄒoㄒ)/~~ 我的神呐…还有啥,还能怎么筛?

(以下纯属脑洞) 闭上眼睛思考的间隙,我去到未来,也就是现在啦,学会了这种线性筛素数的方法。

╭(╯^╰)╮哼!等我回来,甩你一脸,叫你不耐烦!没(T)错(T)!说的就是你!

线性筛法


贫了半天,不废话了,直接上代码,据说是某搞OI的大神写出来的,来源已无从考证:

1234567891011121314151617181920212223242526

void PrintPrimer(int n){ bool check[n]; // 标志位数组,判断与下标对应的数字是否为素数 int prime[n]; // 存储素数 memset(check, true, n); memset(prime, 0, n); int pos = 0; // prime数组当前位置下标 for(int i = 2; i <= n; i++) { if(check[i]) // i是素数 prime[pos++] = i; for(int j = 0; j < pos && i * prime[j] <= n; j++) { check[i * prime[j]] = false; // 筛掉,i * prime[j]不是素数 if(i % prime[j] == 0) break; } } for(int i = 0; i < pos; i++) cout << prime[i] << endl;}

以上算法其实有个名字,即欧拉筛法,专门用于筛选素数,思想也不复杂:当一个数为素数的时候,它的倍数肯定不是素数。所以可以从2开始通过乘积筛掉所有的合数,将所有合数标记,保证不被重复筛除,时间复杂度为 $O(n)$,由于它复杂度是线性的,所以特别适合于大数据量的场景。

咋一看,算法阐述起来和普通的筛法并无二致,实际上,两者最重要的区别就在于:

有无重复筛除

为什么有这个问题呢?我们不妨回顾一下:

在普通筛法中,假设当前访问到一个素数2,那么接下来就会将指定范围内的2的倍数全部标记为非素数,比如 $6=2\times3$,即在当前访问到的素数为2时,6会被2筛除。当2的倍数被筛除完毕,应该访问下一个素数3,而 $6=3\times2$,即6也会被3筛除,这就造成了重复筛除,使得普通筛法的时间复杂度无法达到线性。

那么,欧拉筛法是如何做到不重复的筛除呢?一句话概括就是:

每个数都只按不超过其最小质因数的质数来筛除其倍数

比如2,其最小质因数为2,不超过2的质数只有2一个,因此,遍历到2时就只会筛除 $2\times2=4$,而不会筛除6,10,14等更大的2的质数倍的数。 再比如5,其最小质因数为5,不超过5的质数有2,3和5,因此,遍历到5时就只会筛除 $5\times2=10$,$5\times3=15,$5\times5$,而不去筛除35,55,65等更大的5的质数倍的数。

到这里我们理解了思想,到底要如何实现呢?再回头看看本节开篇的那段代码:

用最笨的方法来看,我们手写出算法的执行过程,试图从中找到规律:


当 $i=2$ 时,$prime[0]=2,pos=1$,此时进入内层 $for$ 循环: $j=0$ 时,会筛除掉 $i \times prime[j]=2\times2=4$,接下来判断 $i \% prime[j]=2 \% 2=0$,故跳出内层循环,从而本轮外循环也结束。


当 $i=3$ 时,$prime[1]=3,pos=2$,此时进入内层 $for$ 循环: $j=0$ 时,会筛除掉 $i \times prime[j]=3\times2=6$,接下来判断 $i \% prime[j]=3 \% 2 \neq 0$,继续内层循环。 $j=1$ 时,会晒出掉 $i \times prime[j]=3\times3=9$,接下来判断 $i \% prime[j]=3 \% 3=0$,故跳出内层循环,从而本轮外循环也结束。


当 $i=4$ 时,已经被2筛除,非素数,此时直接进入内层 $for$ 循环: $j=0$ 时,会筛除掉 $i \times prime[j]=4\times2=8$,接下来判断 $i \% prime[j]=4 \% 2=0$,故跳出内层循环,从而本轮外循环也结束。


当 $i=5$ 时,$prime[2]=5,pos=3$,此时进入内层 $for$ 循环: $j=0$ 时,会筛除掉 $i \times prime[j]=5\times2=10$,接下来判断 $i \% prime[j]=5 \% 2 \neq 0$,继续内层循环。 $j=1$ 时,会筛除掉 $i \times prime[j]=5\times3=15$,接下来判断 $i \% prime[j]=5 \% 3 \neq 0$,继续内层循环。 $j=2$ 时,会筛除掉 $i \times prime[j]=5\times5=25$,接下来判断 $i \% prime[j]=5 \% 5=0$,故跳出内层循环,从而本轮外循环也结束。


从以上执行过程,不难发现:

当 $i$ 为素数时,会首先将自己添加到素数存储数组中 $prime$ 中,然后进入内层 $for$ 循环中筛除其倍数,直至 $i \% prime[j]==0$,而 $i$ 是素数,仅有一个质因数,即其本身,也就是说当前遍历到的数为 $i$ 时,会筛除 $i$ 与全部不超过其最小质因数($i$ 本身)的素数之积; 当 $i$ 为非素数时,已经被前面的素数筛除掉,即不能将自己添加到素数存储数组 $prime$ 中,因此直接进入内层 $for$ 循环中筛选其倍数,直至 $i \% prime[j]==0$,而 $i$ 是非素数,可能有多个质因数,而要满足该跳出循环的条件,$prime[j]$ 就是 $i$ 的最小质因数,从而会在内层循环中筛除 $i$ 与全部不超过其最小质因数($prime[j]_{min}$)的素数之积。

整合两种情况,得出以下结论:

每次遍历到一个数 $i$,无论素数与否,都会筛除数 $i$ 与其全部不超过其最小质因数的素数之积

还是不够直观是吧,那再看下面这张表:

$i$

$prime[0] \times i$

$prime[1] \times i$

$prime[2] \times i$

$prime[3] \times i$

$prime[4] \times i$

2

$2 \times 2$

3

$3 \times 2$

$3 \times 3$

4

$4 \times 2$

5

$5 \times 2$

$5 \times 3$

$5 \times 5$

6

$6 \times 2$

7

$7 \times 2$

$7 \times 3$

$7 \times 5$

$7 \times 7$

8

$8 \times 2$

9

$9 \times 2$

$9 \times 3$

10

$10 \times 2$

11

$11 \times 2$

$11 \times 3$

$11 \times 5$

$11 \times 7$

$11 \times 11$

第一列即筛除掉全部以2为最小质因数的数,第二列筛除掉全部以3为最小质因数的数…依次类推,可以把所有的合数都筛掉。

因为是按照最小素因子筛选,所以可以保证每个数都只会被筛一遍。

上面是我的通俗理解,下面援引自此篇,感觉分析得更为严谨,也放在这里供大家参考:

这段代码最难理解的是这句:

1

if (i % prime[j] == 0) break;

要理解这句话,(顺便不严谨地)证明这个算法的时间复杂度和正确性,要从以下两个方面: 每个数至少被访问一次 对于质数,一定会在 $i$ 的循环中访问到,并确定为质数。 对于合数,因为每一个合数都可以表示成它最小的质因数和另一个数的乘积,而我们枚举了所有的另一个数(也就是 $i$),所以它一定会被它的最小质因数筛掉。 每个数至多被访问一次 对于质数,不可能在 $j$ 的循环中被访问到,因此仅会在 $i$ 的循环中被访问到恰好一次。 对于合数,对于 $i = i_1 = p \times a$,因为在 $i_1 \% prime[j_1] == 0$ 时 $break$,所以不可能出现一个数 $x=i_1 \times prime[k]=p \times a \times prime[k] (k > j_1)$ 在 $i = i_1, j = k$ 的时候被筛掉一次,又在 $i = a \times prime[k]$ 的时候被 $p$ 给筛掉的情况。 综上所述,每个数被访问一次且仅访问一次!因此整个算法的复杂度是 $O(n)$ 的。

面试结果


hmmmmmmmm… 当然,很愉快的,即使是在面试官迟到了1小时的情况下,TT还是很给面子,没让我过,我记住了,哼! 不过好事多磨,总有收获还是不错的啦~再接再厉!

参考资料


[1]菜鸟学线性筛素数 [2]欧拉筛法找素数 [3]求1000000以内的素数 [4]线性时间内筛素数和欧拉函数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术翻译

10个用于人工智能的开源工具/框架

TensorFlow™是一个开源软件库,最初由研究Google Brain Team的研究人员和工程师开发。TensorFlow用于使用数据流图进行数值计算。图...

1.3K2
来自专栏灯塔大数据

洞察|美国大选倒计时:R 语言和蒙特卡洛算法预测希拉里赢面高达89%

距总统大选不到一周,来预测一下竞选结果还是很有挺有趣的。虽然关于选举,有的是博客和网站的预测,但确切告诉你他们究竟用了什么模型,或者告诉你怎么做这个预测的却寥...

3819
来自专栏CDA数据分析师

资源 | 工程师必备!最好的九张机器学习;深度学习代码速查

作者在 Github 上建立了一个代码速查表,对机器学习初学者来说是不可多得的一个资源。文章中的高清图片附加百度网盘,读者可从中浏览,也可以点击项目地址或文后的...

2339
来自专栏技术翻译

关于TensorFlow你应该知道的9件事

TensorFlow是一个机器学习框架。如果你有大量的数据或你在人工智能中追求的最先进的东西,那么这个框架可能是你最好的选择:深度学习。

950
来自专栏AI科技评论

动态 | ACL 2018 公布四篇最佳 demo 候选论文,三篇论文第一作者来自中国

雷锋网 AI 科技评论按:7 月 9 日,自然语言处理顶会 ACL 公布了最佳 demo 论文的四篇候选论文,名单如下:

1414
来自专栏数据派THU

盘点数据科学20个最好的Python库(附链接)

本文约3000字,建议阅读6分钟。 本文将给大家介绍数据科学领域20个最好的Python库。

1225
来自专栏专知

Smart Compose:神经网络辅助写邮件

2002
来自专栏大数据文摘

手把手:AlphaGo有啥了不起,我也能教你做一个(附Python代码)

2435
来自专栏AI研习社

用机器学习搞艺术,谷歌 Megenta 项目集锦(附 Github)

雷锋网 AI 研习社按:本文为雷锋字幕组编译的技术博客,原文 Make Music and Art Using Machine Learning,作者 mage...

1652
来自专栏Bingo的深度学习杂货店

我分析了2837首歌曲,做了个信息检索与信息抽取系统

我把目标锁定在网易云音乐热门的华语男歌手、华语女歌手以及华语组合/乐队,每一类爬取20个热门歌手,这样我就有了60位歌手的信息。

1561

扫码关注云+社区

领取腾讯云代金券