首页 > 代码库 > 睡前数学一小时之线性筛素数：
睡前数学一小时之线性筛素数：
睡前数学一小时之线性筛素数：
1，朴素的筛素数算法：埃拉托斯特尼筛法。
这是个简单再简单不过的一个素数的筛法。只是名字很拉风。这就告诉我们，往往东西不好这没什么，名字很拉风。别人也不会记住。hhhhh。
这个的思路就是。每一个数都是由一个质数与和数(质数也可以)的积组成。这也是质数与和数的定义。而这个它这个筛发，就是当遇到一个质数的时候开始枚举，枚举［1，n］中间关于这个质数的倍数。每次都枚举，每次都将算出的这个数打上标记。而最后整个区间内的质数枚举完后，整个区间内的质数也就筛选出来了。
这个很简单。
时间复杂度是O（N logN logN）.本人觉得其实在区间100000000之间，这个算法都不会炸。但是不是很推荐这个，1，有点慢，一个数会被筛好几次。2，一点都不装B。。不过。存在必有其道理。这个也有它的用处。
1 #include<cstdio> 2 int p[100010],f[100010]; 3 int main() 4 { 5 int n,cnt=0; 6 scanf("%d",&n); 7 for(int i=2;i<=n;i++) 8 { 9 if(f[i]==0)10 {11 p[++cnt]=i;12 for(int j=2;i*j<=n;j++)13 {14 f[i*j]=1;15 }16 }17 }18 for(int i=2;i<=n;i++)19 {20 if(f[i]==0)printf("%d ",i);21 }22 return 0;23 }
2，欧拉线性筛法：一个很♀快的筛法，这个求什么函数也是很厉害。很可惜，不会。
而这个筛法的思路就有点绕了。就将一个和数拆成一个最小质因子乘，和数或者是质数。认真思考一下。这样的话。如果保证是最小的质因子。那每个数也就只筛一遍。不用重复筛选。诶！这个不就快起来了。／
这个时间复杂度就只有O(N)明显要比那个埃拉托斯特尼筛法快。但是这个筛法还有其它的用处。所以这个得去了解。
嗯。接下来是代码。
1 #include<cstdio> 2 int p[100010],f[100010]; 3 void Euler() 4 { 5 int n,cnt=0; 6 scanf("%d",&n); 7 for(int i=2;i<=n;++i) 8 { 9 if(f[i]==0)10 p[++cnt]=i;11 for(int j=1;j<=cnt&&i*p[j]<=n;++j)12 {13 f[i*p[j]]=1;14 if(i%p[j]==0)break;15 }16 }17 return ;18 }
睡前数学一小时之线性筛素数：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。