文章目录
  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;
}

欧拉筛法

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