前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >素数筛选算法

素数筛选算法

作者头像
我是东东东
发布于 2018-08-01 09:16:33
发布于 2018-08-01 09:16:33
1.1K0
举报
文章被收录于专栏:我是东东强我是东东强

全文概要

最近学习了一种筛素数的方法,能够以时间复杂度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]线性时间内筛素数和欧拉函数

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-05-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
WCF后续之旅(15): 逻辑地址和物理地址
在WCF中,每个终结点都包含两个不同的地址——逻辑地址和物理地址。逻辑地址就是终结点Address属性表示的地址。至于物理地址,对于消息发送放来讲,就是消息被真正发送的目的地址;而对于消息的接收放来讲,就是监听器真正监听的地址。 一、服务端的物理地址 在默认的情况下,终结点的逻辑地址和物理地址是同一个URI。换句话说,终结的逻辑地址是必须的,如何物理地址没有指定的,默认使用逻辑地址作为物理地址。对于消息接收方的终结点来讲,物理地址就是监听地址,通过ServiceEndpoint的ListenUri表示:
蒋金楠
2018/01/16
8350
WCF后续之旅(15): 逻辑地址和物理地址
WCF服务端运行时架构体系详解[上篇]
WCF的服务端架构体系又可以成为服务寄宿端架构体系。我们知道,对于一个基于某种类型的服务进行寄宿只需要使用到一个唯一的对象,那就是ServiceHost。甚至在某种语境下,我们所说的服务实际上就是指的对应的ServiceHost对象。整个服务寄宿过程包括两个阶段,即服务描述的创建和服务端运行框架的建立。而第一个阶段创建的服务描述是为了第二个阶段对服务端运行时框架建立服务的,所以我们有必要在对服务描述进行简单的介绍。 目录: 一、从服务描述(Service Description)谈起
蒋金楠
2018/02/07
7120
WCF服务端运行时架构体系详解[上篇]
WCF配置文件与文件下载之坎坷路
题外话:本以为我会WCF了,精通WCF了,毕竟刚做过一个WCF的项目,不就是写写契约接口,然后实现接口,改下配置。最后用控制台或者服务发布一下,不就能用了。不就是简单ABC吗?不是So Easy吗?做第二个项目的时候我悲剧了,被碰的头破血流!忽然发现什么什么都不会(第一个项目比照网上教程一步一步弄的),连写一个简单hello world都写不出来。我之前还以为自己很懂了…… 一、WCF文件配置       为了不重蹈覆辙,这次争取把他整懂整透(当然这才是入门而已)。WCF很强大,它的强大跟它的配置有很大的
hbbliyong
2018/03/06
1.2K0
[WCF 4.0新特性] 默认终结点
很多WCF的初学者是从之前的Web服务上转移过来的,他们非常怀念.asmx Web服务无配置的服务寄宿方式。你只需要在定义Web服务的时候再表示服务操作的方法上应用WebMethodAttribute特性就可以了,完全可以不需要手工进行相应的配置,因为Web服务运行时会自动为你添加默认的配置。但是对于WCF来说,在进行服务寄宿的时候,你必须以编程或者配置的方式为服务添加至少一个终结点,而终结点需要具备基本的ABC三要素。 对于最新版本的WCF编程人员来说,你也可以采用无配置的服务寄宿了,这主要得益于WCF提
蒋金楠
2018/02/07
8000
WCF技术剖析之二十: 服务在WCF体系中是如何被描述的?
任何一个程序都需要运行于一个确定的进程中,进程是一个容器,其中包含程序实例运行所需的资源。同理,一个WCF服务的监听与执行同样需要通过一个进程来承载。我们将为WCF服务创建或指定一个进程的方式称为服务寄宿(Service Hosting)。服务寄宿的本质通过某种方式,创建或者指定一个进程用以监听服务的请求和执行服务操作,为服务提供一个运行环境。 服务寄宿的方式大体分两种:一种是为一组WCF服务创建一个托管的应用程序,通过手工启动程序的方式对服务进行寄宿,所有的托管的应用程序均可作为WCF服务的宿主,比如C
蒋金楠
2018/01/16
1.1K0
快速入门系列--WCF--01基础概念
转眼微软的WCF已走过十个年头,它是微软通信框架的集大成者,将之前微软所有的通信框架进行了整合,提供了统一的应用方式。记得从自己最开始做MFC时,就使用过Named Pipe命名管道,之后做Winform时,使用过Remoting,再之后做B/S架构时,就会经常使用.NET平台下的Web Service,直到使用上WCF。看上去有了一些WCF的使用经验,实则不然,比如对安全、分布式事务、可靠会话等主题仍然接触甚少,因而决定重新回顾学习一下相关知识,尤其是对WCF框架的理解(已于2015年开源,可下载源码,h
用户1216676
2018/01/24
1.1K0
快速入门系列--WCF--01基础概念
菜菜从零学习WCF三(配置服务)
在设计和实现服务协定后,即可配置服务。在其中可以定义和自定义如何向客户端公开服务,包括指定可以找到服务的地址、服务用于发送和接收消息的传输和消息编码,以及服务需要的安全类型。
aehyok
2018/09/11
8450
菜菜从零学习WCF三(配置服务)
我的WCF之旅(1):创建一个简单的WCF程序
为了使读者对基于WCF的编程模型有一个直观的映像,我将带领读者一步一步地创建一个完整的WCF应用。本应用功能虽然简单,但它涵盖了一个完整WCF应用的基本结构。对那些对WCF不是很了解的读者来说,这个例子将带领你正式进入WCF的世界。 在这个例子中,我们将实现一个简单的计算服务(CalculatorService),提供基本的加、减、乘、除的运算。和传统的分布式通信框架一样,WCF本质上提供一个跨进程、跨机器以致跨网络的服务调用。在本例中,客户端和服务通过运行在相同的同一台机器上不同进程模拟,图1体现了客户端
蒋金楠
2018/02/07
9600
我的WCF之旅(1):创建一个简单的WCF程序
WCF系列教程之WCF服务配置工具
本文参考自http://www.cnblogs.com/wangweimutou/p/4367905.html Visual studio 针对服务配置提供了一个可视化的配置界面(Microsoft
郑小超.
2018/01/26
1K0
WCF简单教程(3) 试着去掉配置文件
通过配置文件来设置Host、Endpoint、Binding等是WCF中推荐的方法,这样可以使发布尽量灵活。其实配置文件中的值,最终还是要体现到代码中的,只不过这部分工作由底层帮你做了。我们今天来尝试去掉配置文件,用纯代码实现发布过程,同时加深一下对层次关系的理解。
py3study
2020/01/07
5160
WCF技术剖析之二十七: 如何将一个服务发布成WSDL[基于WS-MEX的实现](提供模拟程序)
通过《如何将一个服务发布成WSDL[编程篇]》的介绍我们知道了如何可以通过编程或者配置的方式将ServiceMetadataBehavior这样一个服务形式应用到相应的服务上面,从而实现基于HTTP-GET或者WS-MEX的元数据发布机制。那么在WCF内部具体的实现原理又是怎样的呢?相信很多人对此都心存好奇,本篇文章的内容将围绕着这个主题展开。 一、 从WCF分发体系谈起 如果读者想对WCF内部的元数据发布机制的实现原理有一个全面而深入的了解,必须对WCF服务端的分发体系有一个清晰的认识。在这里我们先对
蒋金楠
2018/01/16
7990
WCF技术剖析之二十七: 如何将一个服务发布成WSDL[基于WS-MEX的实现](提供模拟程序)
我的WCF之旅(2):Endpoint Overview
WCF实际上是构建了一个框架,这个框架实现了在互联系统中各个Application之间如何通信。使得Developers和Architect在构建分布式系统中,无需在考虑如何去实现通信相关的问题,更加关注与系统的业务逻辑本身。而在WCF Infrastructure中,各个Application之间的通信是由Endpoint来实现的。 Endpoint的结构 Endpoint包含以下4个对象: Address: Address通过一个URI唯一地标识一个Endpoint,并告诉潜在的WCF service
蒋金楠
2018/02/07
8680
我的WCF之旅(2):Endpoint Overview
WCF技术剖析之二十七: 如何将一个服务发布成WSDL[编程篇]
对于WCF服务端元数据架构体系来说,通过MetadataExporter将服务的终结点导出成MetadataSet(参考《如何导出WCF服务的元数据》),仅仅是完成了一半的工作。被成功导出的以MetadataSet对象表示的元数据需要最终作为可被访问的网络资源发布出来,才能被服务消费者获取,进而有效地帮助他们进行服务调用。元数据的发布最终是通过ServiceMetadataBehavior这样一个服务行为实现的,我们先来认识一下ServiceMetadataBehavior。 一、 元数据发布的实现者:S
蒋金楠
2018/01/16
7980
快速入门系列--WCF--08扩展与新特性
最后一章将进行WCF扩展和新特性的学习,这部分内容有一定深度,有一个基本的了解即可,当需要自定义一个完整的SOA框架时,可以再进行细致的学习和实践。 服务端架构体系的构建主要包含接下来的几个要素:服
用户1216676
2018/01/24
6500
快速入门系列--WCF--08扩展与新特性
关于WCF的一个非常“无语”的BUG!
这确实是一个让人觉得“无语”的BUG,甚至让我觉得微软在故意和我们开玩笑。这个问题在我刚刚接触WCF的时候就遇到过,换言之,这个问题一直存在于.NET 3.0、3.5和现在的4.0。这是一个关于在你对WCF进行扩展的时候会经常碰到的问题,读者朋友们可以根据下面的步骤来再现这一个问题。 创建自定义行为(服务行为、终结点行为、契约行为和操作行为)是对WCF进行扩展最为常用的形式。通过下面的代码,我们创建了一个自定义的服务行为,为了简单我们没有编写任何逻辑代码。 1: namespace Artech.Bu
蒋金楠
2018/01/16
4920
关于WCF的一个非常“无语”的BUG!
[WCF-Discovery] 实例演示:如何利用服务发现机制实现服务的“动态”调用?
前面两篇(《服务如何能被”发现”》和《客户端如何能够“探测”到可用的服务?》)我们分别介绍了可被发现服务如何被发布,以及客户端如果探测可用的服务。接下来我们通过一个简单的例子来演示如果创建和发布一个可被发现的服务,客户端如何在不知道服务终结点地址的情况下动态探测可用的服务并调用之。该实例的解决方案采用如右图所示的结构,即包含项目Service.Interface(类库)、Client(控制台应用)和Service(控制台应用)分别定义服务契约、服务(包括服务寄宿)和客户端程序。[源代码从这里下载,Dyn
蒋金楠
2018/02/07
6620
[WCF-Discovery] 实例演示:如何利用服务发现机制实现服务的“动态”调用?
WCF技术剖析_学习笔记之一
本系列适合新手,从0学起。共同学习,共同探讨。 基础概念 SOA:就是采用Web服务的架构 它有一些特性,需要了解: 1、自治的:不依赖于访问它的客户端和其他服务,可以独立的进行部署和实施版本策略和安全策略。 2、依赖于开放的标准:让不同的厂商开发的服务能够进行互操作。 3、支持跨平台 4、鼓励创建可组合的服务 5、鼓励服务的复用 6、强调松耦合:契约的实现 WCF应用实例,帮助理解WCF服务的基本结构 过程: 1、构建解决方案 Contracts:定义服务的契约(接口部分) Services:定义服务的实
小端
2018/04/16
5380
WCF技术剖析_学习笔记之一
创建一个自托管(Self-Host)的WCF Service
若确保上述self-host server能运行,需要用管理员权限开一个powershell,运行:
用户10555056
2023/05/25
4720
WCF浅尝
1.首先先建立一个WCF服务应用程序 2.再建立一个宿主程序,这里用控制台,添加服务引用,这里会报错: 点击页面确定,回到添加服务页面 点击箭头有如下内容: 这里告诉我们问题的所在,我们只要重新生成解
hbbliyong
2018/03/06
9340
WCF浅尝
WCF 学习总结2 -- 配置WCF
前面一篇文章《WCF 学习总结1 -- 简单实例》一股脑儿展示了几种WCF部署方式,其中配置文件(App.config/Web.config)都是IDE自动生成,省去了我们不少功夫。现在回过头来看看IDE提供的Wcf Service Library项目模板中的默认服务端配置文件——App.config里面究竟有什么秘密。 服务端的配置文件主要是对services、bindings、behaviors的配置。在默认的App.config中,使用的是WCF Framework定义好的wsHttpBinding默
hbbliyong
2018/03/05
1.1K0
WCF 学习总结2 -- 配置WCF
推荐阅读
相关推荐
WCF后续之旅(15): 逻辑地址和物理地址
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档