质数线性筛

116 阅读 0 评论 77 点赞

我是靠谱客的博主听话小甜瓜，这篇文章主要介绍质数线性筛，现在分享给大家，希望可以做个参考。

其实基本的素数筛，时间复杂度也能到达O(n*loglogn)，线性筛的提速并不是很明显，但这种思想还是值得学习的，这一版本是基于合数都可拆解为几个质因数相乘，只用用最小质因数筛一遍实现O（n）的复杂度。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void as(int n)
{
REW(a,0);//0代表是素数。
a[0]=a[1]=1;
t=0;
FOR(i,2,n)
{
if(!a[i])
b[++t]=i;
FOR(j,1,t)
{
if(1ll*i*b[j]>n)
break;//long long防止溢出。
a[b[j]*i]=1;
if(i%b[j]==0)
break; //最重要的一句，可以保证所有数只最小的质因数被筛一遍。
}
}
}