欧拉筛学习笔记
线性筛质数
代码
1 | int prime[MAXN],tot; |
分析
算法分析
考虑你在设计一个线性筛质数算法
你想,既然要做到“线性”,那么每个数必须只能被筛一次
所以我们猜想,一个合数只会被它的最小素因数筛去
代码分析
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 | if(is_prime[i]) |
如果它在之前的筛选中“存活”下来,那么它一定是个素数,把它加入素数列表
1 | for(int j=1;j<=tot&&i*prime[j]<=n;j++) |
枚举i
与一个素数能组成的所有合数,注意不要让它们超过n
1 | is_prime[i*prime[j]]=0; |
标记为合数
1 | if(i%prime[j]==0) |
关键一步
如果i
可以有一个素数因子,就跳出循环
为什么呢?
我们先来看线性筛质数的规则:
一个合数只会被它的最小素因数筛去
如果i
有别的素因数了,那么证明它不是接下来的合数的最小素因数
所以为了保证运行效率,要跳出循环
时间复杂度
$$ T(N) = O(N) $$
参考文献
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.