文章目录
  1. 1. 埃拉托斯特尼筛法
  2. 2. 欧拉筛法

引言:总是会忘记素数筛的写法,在这里写一下加强记忆。


这个素数筛的时间复杂度是接近O(n)O(n)的,叫做埃拉托斯特尼筛法,怎么样,是不是被这个牛逼名字震撼到了?实际上它的复杂度是O(nlog(log(n)))O(nlog(log(n))),嗯复杂度也很牛逼。但还有更牛逼的筛法叫欧拉筛,复杂度是O(n)O(n),巧了,我不会。传送门:线性筛和积性函数

埃拉托斯特尼筛法

  • 这个埃氏筛,就是将2~n中,从小到大挑一个数,比方说2吧,把2放进素数数组里,把2及2的倍数都标记为已访问,表示它们除了2都是非素数,这些数我已经确认身份了。然后挑个3,把3放进素数数组里,把3及3的倍数都标记为已访问。然后是4,4已访问跳过,再看5,5未访问,把5放进素数数组里,将5和5的倍数标记为已访问。一直到n。
  • 下面这个代码将vis数组和prime数组合并了,条件是:筛到某素数时,一定有素数值大于已得到的素数个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <cstring>

int prime[1000];
int main()
{
int cnt=0;
for(int i=2;i<1000;i++)
{
if(!prime[i])//充当vis数组
{
prime[cnt++]=i;//这里是prime数组
for(int j=i+i;j<1000;j+=i)
prime[j]=1;//充当vis数组
}
}
for(int i=0;i<cnt;i++)
printf("%d ",prime[i]);
return 0;
}

欧拉筛法

https://blog.csdn.net/nuanxin_520/article/details/41207145

1
2
3
4
5
6
7
8
9
10
int tot=0;
for(int i=2;i<maxn;++i){
if(!vis[i]) primes[tot++]=i;
for(int j=0;j<tot;++j){
int t=i*primes[j];
if(t>maxn) break;
vis[t]=1;
if(i%primes[j]==0) break;
}
}

如果遇到i为合数,我们只认为合数由一个最小的素数*合数得到

ii可以被素数primes[j]primes[j]除时,则没必要用primes[j+1]primes[j+1]去筛掉iprimes[j+1]i*primes[j+1]了,因为iprimes[j+1]i*primes[j+1]这个数将来一定会被primes[j]primes[j]筛掉的。用数学归纳法易证。

文章目录
  1. 1. 埃拉托斯特尼筛法
  2. 2. 欧拉筛法