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

素数筛选算法

全文概要

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

相关文章

  • 素数筛选

    思路:我们知道素数的倍数肯定不是素数,所以的话,我们将素数的倍数置为1,经过这一系列处理后,遍历输出为0的即求出了N以内的所有素数!

    杨鹏伟
  • 素数(质数)筛选法模板

    echobingo
  • [每日一题]欧拉筛选法判断素数

    今天给大家的是一种效率比较高(逼格一样高哦)的方法,叫欧拉线性筛选法 题目描述 用筛法求之N内的素数。 输入 N 输出 0~N的素数 样例输入 100 样例输出...

    编程范 源代码公司
  • 素数筛法(Eratosthenes筛法)

    Eratosthenes筛法,又名埃氏筛法,对于求1~n区间内的素数,时间复杂度为n log n,对于10^6^ 以内的数比较合适,再超出此范围的就不建议用该方...

    _DIY
  • 数学--数论--HDU 2136(素数筛选法)

    Everybody knows any number can be combined by the prime number. Now, your task ...

    风骨散人Chiam
  • 算法模板——线性筛素数

    实现功能:如题,筛出1——N内的所有素数 原理:如phile神犇所言,这次的才算是真正意义上的线性筛素数,其精髓在于if (i mod a[j])=0 then...

    HansBug
  • HDOJ 1397 Goldbach's Conjecture(快速筛选素数法)

    Problem Description Goldbach’s Conjecture: For any even number n greater than ...

    谙忆
  • 素数的筛法

    素数的筛法有很多种 在此给出常见的三种方法 以下给出的所有代码均已通过这里的测试 埃拉托斯特尼筛法 名字好长 :joy:  不过代码很短 思路非常简单,对于每一...

    attack
  • 筛法求素数

    根据素数定义可知,若某个数能被其他素数整除,则其一定不为素数,因此可以依次筛掉1 ~ N中不是素数的数,剩下的即为所求。

    你的益达
  • Python使用集合实现素数筛选法

    首先生成指定范围内的所有自然数,然后从前往后遍历其中的数字,并分别删除这些数字的倍数,最后剩下的数字都是素数。 很久很久以前,曾经写过一个使用列表+filter...

    Python小屋屋主
  • Python使用筛选法计算小于给定数字的所有素数

    代码思路:首先列出指定范围内所有候选数字,然后从前往后依次选择一个数字去除以后面所有数字,能够被整除的肯定不是素数,把这些数字过滤掉,然后重复这个过程,直到选择...

    Python小屋屋主
  • 素数间隙的组合筛算法(CS)

    素数差是连续素数之间的差。每一个间隙的最小素数都有记录。例如,最小质数后接4的间隙为7;6的间隙在23之后;96的间隙在360653之后。在2019年去世之前,...

    用户8054111
  • 筛法求素数质数

    埃拉托斯特尼筛法 ,简称 埃氏筛 或 爱氏筛 ,是一种由希腊数学家 埃拉托斯特尼 所提出的一种简单 检定素数 的算法。要得到自然数n以内的全部素数,必须把不大于...

    机器学习和大数据挖掘
  • jquery 筛选元素(1)

    .eq()   减少匹配元素的集合为指定的索引的那一个元素。   .eq(index)     index一个整数,指示元素的位置,以0为基数。  ...

    用户1197315
  • jquery 筛选元素 (2)

    .add()   创建一个新的对象,元素添加到匹配的元素集合中。   .add(selector)     selector 一个字符串表示的选择器...

    用户1197315
  • jquery 筛选元素 (3)

    .addBack()   添加堆栈中元素集合到当前集合中,一个选择性的过滤选择器。   .addBack([selector]) ...

    用户1197315
  • 筛法求素数 6分

    11:回文素数 查看 提交 统计 提问 总时间限制: 5000ms 内存限制: 65536kB描述一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文...

    attack
  • HDOJ(HDU) 2136 Largest prime factor(素数筛选)

    Problem Description Everybody knows any number can be combined by the prime nu...

    谙忆
  • HDOJ/HDU 2710 Max Factor(素数快速筛选~)

    Problem Description To improve the organization of his farm, Farmer John label...

    谙忆

扫码关注云+社区

领取腾讯云代金券