专栏首页我是东东强素数筛选算法

素数筛选算法

全文概要

最近学习了一种筛素数的方法,能够以时间复杂度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 条评论
登录 后参与评论

相关文章

  • Git工作区、版本库与暂存区

    Git与其它版本控制系统如SVN的一个最大的不同之处就是发明了暂存区的概念,本文从创建Git版本库开始,依次描述了追踪文件、修改文件、丢弃修改、提交修改等基本G...

    我是东东东
  • 网络互连设备小结

    计算机网络往往由多种不同类型的网络通过特殊的设备相互连接而成,本文简要介绍了转发器、集线器、网桥、桥接器、交换机、路由器等多种网络互连设备的功能原理。

    我是东东东
  • 交换机与路由器详细比较

    作为计算机网络中最重要的两种数据包转发设备,交换机和路由器在功能设计方面既存在本质差别,又包含诸多相似之处,本文从两种设备的工作原理出发,详细介绍了它们之间的种...

    我是东东东
  • 【Python 第40课】 用文件保存游戏(2)

    话接上回。我们已经能从文件中读取游戏成绩数据了,接下来就要考虑,怎么把我们每次游戏的结果保存进去。 首先,我们需要有一个变量来记录每次游戏所用的轮数: time...

    Crossin先生
  • Json概述以及python对json的相关操作

    JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScr...

    bear_fish
  • vscode格式化vue

    修改步骤 1、点击配置,查看有几个插件同时使用了 2、卸载不需要的插件 3、重新配置

    程序员不务正业
  • 从全备中恢复单库或单表,小心有坑!

    MySQL 逻辑备份工具最常用的就是 mysqldump 了,一般我们都是备份整个实例或部分业务库。不清楚你有没有做过恢复,恢复场景可能就比较多了,比如我想恢复...

    MySQL技术
  • 快速学习-React 生命周期简介

    cwl_java
  • Sublime Text3 python调试之pdb

    最近写关于AStar算法遇到了点问题,需要调试python程序,直接使用print太过于麻烦,于是乎调查了一下python调试的工具,发现这个pdb还真是方便。

    李小白是一只喵
  • 学界 | 反超GPU:微软提出在CPU上高效解码的神经机器翻译模型

    选自arXiv 机器之心编译 参与:黄玉胜、李泽南 在最近一次机器学习热潮中,GPU 一直是承担神经网络模型训练和处理的主要计算设备,大多数模型都是针对 GPU...

    机器之心

扫码关注云+社区

领取腾讯云代金券