素数的筛法

素数的筛法有很多种

在此给出常见的三种方法

以下给出的所有代码均已通过这里的测试

埃拉托斯特尼筛法

名字好长 :joy:  不过代码很短

思路非常简单,对于每一个素数,枚举它的倍数,它的倍数一定不是素数

这样一定可以保证每个素数都会被筛出来

还有,我们第一层循环枚举到\sqrt(n)就好,因为如果当前枚举的数大于n,那么它能筛出来的数一定在之前就被枚举过

比如说:

\sqrt(100)=10

不难发现我们从20枚举所筛去的数一定被5筛过

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 const int MAXN=10000001;
 5 inline int read()
 6 {
 7     char c=getchar();int f=1,x=0;
 8     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
 9     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN];
12 int n,m;
13 int main()
14 {
15     n=read();m=read();
16     vis[1]=1;//1不是质数
17     for(int i=2;i<=sqrt(n);i++)
18         for(int j=i*i;j<=n;j+=i)
19             vis[j]=1;
20     while(m--)
21     {
22         int p=read();
23         if(vis[p]==1)    printf("No\n");
24         else             printf("Yes\n");
25     }
26     return 0;
27 }

但是你会发现这份代码只能得30分

看来这种算法还是不够优秀

下面我们来探索一下他的优化

另外,这种算法的时间复杂度:$O(n*logn)$

埃拉托斯特尼筛法优化版

根据唯一分解定理

每一个数都可以被分解成素数乘积的形式

那我们枚举的时候,只有在当前数是素数的情况下,才继续枚举就好

这样可以保证每个素数都会被筛出来

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 const int MAXN=10000001;
 5 inline int read()
 6 {
 7     char c=getchar();int f=1,x=0;
 8     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
 9     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN];
12 int n,m;
13 int main()
14 {
15     n=read();m=read();
16     vis[1]=1;//1不是质数
17     for(int i=2;i<=sqrt(n);i++)
18         if(vis[i]==0)
19             for(int j=i*i;j<=n;j+=i)
20                 vis[j]=1;
21     while(m--)
22     {
23         int p=read();
24         if(vis[p]==1)    printf("No\n");
25         else             printf("Yes\n");
26     }
27     return 0;
28 }

果然,加了优化之后这种算法快了不少

可以证明,它的复杂度为:O(n*log^{logn})

这种算法已经非常优秀了,但是对于1e7这种极端数据,还是有被卡的风险

那么,还有没有更快的筛法呢?

答案是肯定的!

欧拉筛

我们思考一下第二种筛法的运算过程

不难发现,对于6这个数,它被2筛了一次,又被3筛了一次

第二次筛显然是多余的,

我们考虑去掉这步运算

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 const int MAXN=10000001;
 5 inline int read()
 6 {
 7     char c=getchar();int f=1,x=0;
 8     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
 9     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN],prime[MAXN];
12 int tot=0;
13 int n,m;
14 int Euler()
15 {
16     vis[1]=1;
17     for(int i=2;i<=n;i++)
18     {
19         if(vis[i]==0)    prime[++tot]=i;
20         for(int j=1;j<=tot&&i*prime[j]<=n;j++)
21         {
22             vis[i*prime[j]]=1;
23             if(i%prime[j]==0)    break;
24         }
25     }
26 }
27 int main()
28 {
29     n=read();m=read();
30     Euler();
31     for(int i=1;i<=m;i++)
32     {
33         int p=read();
34         if(vis[p]==1)    printf("No\n");
35         else             printf("Yes\n");
36     }
37     return 0;
38 }

对于这份代码,我们分情况讨论

当i是素数的时候,那么两个素数的乘积一定没有被筛过,可以避免重复筛

当i不是素数的时候

程序中有一句非常关键的话

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

这句话可以保证:本次循环只能筛出不大于prime[j]*i的数

这样就可以保证一个数只会被它最小的素因子筛去!

也就可以保证每个数只会被筛一次

举个例子,

i=2*3*5,此时能筛去i*2,但是不能筛去3*i

因为如果能晒出3*i的话,

i_2=3*3*5时,筛除2*i_2就和前面重复了

另外为了方便大家直观理解,给出一张图表

 这样显得直观一些

大家好好揣摩揣摩

可以看出这种算法的时间效率是非常高的!

时间复杂度:严格O(n)

总结

在一般情况下,第二种筛法已经完全够用。

第三种筛法的优势不仅仅在于速度快,而且还能够筛积性函数,像欧拉函数,莫比乌斯函数等。

这个我以后还会讲的

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

深度学习入门之工具综述

原文:Getting Started with Deep Learning: A REVIEW OF AVAILABLE TOOLS 作者: MATTHEW R...

379130
来自专栏智能算法

深度学习三人行(第1期)---- TensorFlow爱之初体验

前面十个系列,我们一起学习了机器学习的相关知识,详情可在“智能算法”微信公众号中回复“机器学习”进行查看学习及代码实战。从该期开始,我们将一起学习深度学习相关知...

429140
来自专栏智能算法

深度学习三人行(第2期)---- TensorFlow爱之再体验

上一期,我们一起学习了TensorFlow的基础知识,以及其在线性回归上的初体验,该期我们继续学习TensorFlow方面的相关知识。学习的路上,我们多多交流,...

377100
来自专栏智能算法

机器视觉与计算机视觉的区别?

计算机视觉与机器视觉,首先是应用场景不一样,就像@Vinjn张静 回答的那样:你把摄像头对着人就是CV,对着车间就是MV。 计算机视觉和机器视觉应用场景不同,就...

644110
来自专栏智能算法

麻省理工学院用深度学习教会计算机预测未来

【AI世代编者按】据外媒报道,通过部分基于人脑模型的算法,麻省理工学院的研究员让计算机可以通过分析照片去预测下一时刻的未来。 麻省理工学院计算机科学和人工智能实...

289110
来自专栏智能算法

基于深度学习的目标检测算法综述

摘要: 从2014年开始,目标检测取得了巨大的突破。本文针对目前主流的目标检测方法进行简单的介绍,文章分为两个部分:第一部分介绍R Girshick提出的以R-...

838130
来自专栏智能算法

2016年不可错过的21个深度学习视频、教程和课程

几年之前,深度学习还是机器学习中一个不太受人关注的领域。随着最近神经网络和大数据概念的出现,很多复杂任务的实现已经成为可能。 目前,深度学习已经被应...

392120
来自专栏测试开发架构之路

深度理解 原码, 反码, 补码

本篇文章讲解了计算机的原码, 反码和补码. 并且进行了深入探求了为何要使用反码和补码, 以及更进一步的论证了为何可以用反码, 补码的加法计算原码的减法. 论证部...

30550
来自专栏智能算法

机器学习三人行(系列一)----机器学习花样入门

写在前面 深度学习如火如荼,作为一个IT技术人员,不搞一下深度学习,总有一种活在上个世纪的感觉,因此笔者准备认认真真的搞一下深度学习,努力跟上时代的步伐。话说基...

43190
来自专栏智能算法

理解这25个概念,你的人工智能,深度学习,机器学习才算入门!

人工智能,深度学习,机器学习—无论你在做什么,如果你对它不是很了解的话—去学习它。否则的话不用三年你就跟不上时代的潮流了。 ——马克.库班 马克.库班的这个观点...

380130

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励