线性筛质数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int prime[MAXN],tot;
bool is_prime[MAXN];
void choose(int n)
{
memset(is_prime,1,sizeof(is_prime));
is_prime[1]=0;
for(int i=2;i<=n;i++)
{
if(is_prime[i])
prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
is_prime[i*prime[j]]=0;
if(i%prime[j]==0)
break;
}
}
}

分析

算法分析

考虑你在设计一个线性筛质数算法

你想,既然要做到“线性”,那么每个数必须只能被筛一次

所以我们猜想,一个合数只会被它的最小素因数筛去

代码分析

1
memset(is_prime,1,sizeof(is_prime));

首先假设所有数都是素数

1
is_prime[1]=0;

确定$1$不是素数

1
for(int i=2;i<=n;i++)

枚举所有$[1,N]$区间内的数

1
2
if(is_prime[i])
prime[++tot]=i;

如果它在之前的筛选中“存活”下来,那么它一定是个素数,把它加入素数列表

1
for(int j=1;j<=tot&&i*prime[j]<=n;j++)

枚举i与一个素数能组成的所有合数,注意不要让它们超过n

1
is_prime[i*prime[j]]=0;

标记为合数

1
2
if(i%prime[j]==0)
break;

关键一步

如果i可以有一个素数因子,就跳出循环

为什么呢?

我们先来看线性筛质数的规则:

一个合数只会被它的最小素因数筛去

如果i有别的素因数了,那么坚强证明它不是接下来的合数的最小素因数

所以为了保证运行效率,要跳出循环

时间复杂度

$$ T(N) = O(N) $$

参考文献

  1. 欧拉筛筛素数 - 学委的博客