素数筛

定义

素数筛用于求出\([2,n]\)范围内的质数。

求解算法

埃拉托斯特尼筛法

思路与简单证明

\([2,\sqrt n]\)范围内质数的所有\(\leq n\)的倍数筛掉,剩下的就是质数。

时间复杂度\(O(n\log\log n)\)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// notpri[i] 为 true 时表示 i 不是质数
// pri[] 是质数的序列
// tot 是质数的总数
void cal_pri(int n)
{
k=sqrt(n);
for(int i=2;i<=k;i++)
{
if(notpri[i])continue;
int j=1;
pri[++tot]=i;
while(i*j<n)
{
notpri[i*j]=true;
++j;
}
}
}

欧拉筛

思路与简单证明

枚举\([2,n]\)范围内的所有数\(i\),枚举\([2,i]\)范围内的所有质数\(pri_j\),将\(i\cdot pri_j\)筛掉;

枚举\(pri_j\)时,满足\(i\bmod pri_j=0\)时终止,因为此时\(i\)可以表示为\(pri_j\cdot x\),之后的数\(i\cdot pri_{j+k}\)可以表示为\(pri_j\cdot x\cdot pri_{j+k}\),已经被\(pri_j\cdot x\)筛掉了,这样可以完全避免一个数被重复筛掉。

时间复杂度\(O(n)\)

实现

1
2
3
4
5
6
7
8
9
10
11
12
void cal_pri(int n)
{
for(int i=2;i<=n;++i)
{
if(!notpri[i])pri[++tot]=i;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
notpri[i*pri[j]]=true;
if(!(i%pri[j]))break;
}
}
}
作者

xqmmcqs

发布于

2018-01-21

更新于

2023-03-29

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×