web analytics

睡前数学一小时之线性筛素数:

睡前数学一小时之线性筛素数:
1,朴素的筛素数算法:埃拉托斯特尼筛法。
这是个简单再简单不过的一个素数的筛法。只是名字很拉风。这就告诉我们,往往东西不好这没什么,名字很拉风。别人也不会记住。hhhhh。
这个的思路就是。每一个数都是由一个质数与和数(质数也可以)的积组成。这也是质数与和数的定义。而这个它这个筛发,就是当遇到一个质数的时候开始枚举,枚举[1,n]中间关于这个质数的倍数。每次都枚举,每次都将算出的这个数打上标记。而最后整个区间内的质数枚举完后,整个区间内的质数也就筛选出来了。
这个很简单。
时间复杂度是O(NloglogN).本人觉得其实在区间100000000之间,这个算法都不会炸。但是不是很推荐这个,1,有点慢,一个数会被筛好几次。2,一点都不装B。。不过。存在必有其道理。这个也有它的用处。

  1 #include
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
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 }

 

Post a Comment

You must be logged in to post a comment.