在之前我们学过的最朴素的筛法就是埃氏筛法(埃拉托斯特尼筛法),它的复杂度是 $\Theta (N \log_2(N))$。其实这个朴素的筛法可以进行常数上的优化。还有一种更炫酷的筛法:欧拉筛,即线性筛法,时间复杂度为 $\Theta (N)$。
朴素筛法(埃氏筛法)
之前我们很早就接触的筛法是这样的:
for (int i=2;i<=N;i++)
for (int j=2;j<=N/i;j++) vis[i*j]=false;
另一种写法是:
for (int i=2;i<=N;i++)
for (int j=i+i;j<=N;j+=i) vis[j]=false;
不得不说这个算法的确特别直观:把所有合数都筛掉。维基百科上还有个很形象的图(不得不说维基百科真是个好地方):
吐槽一句,这个筛法全名叫“埃拉托斯特尼筛法”……你知道为什么欧拉筛不叫欧氏筛法而只有这个筛法叫做埃氏筛法吗……
时间复杂度
可以看出,这个算法的计算量是 $\frac n 2 +\frac n 3 +\frac n 4 + \dots$。据说这个是调和级数,可以证明复杂度是 $\Theta (N log_2(N))$。
朴素筛法的优化
这个算法其实可以优化:按照原来的写法,对于合数 $a\ast b$,它会被 $a$ 和 $b$ 筛到,又会被 $b$ 和 $a$ 筛到,相当于被筛到了两次。其实我们可以只枚举较小的那个因子,这样可以优化一半的时间:
for (int i=2;i<=sqrt(n);i++)
for (int j=i*i;j<=n;j+=i) vis[j]=true;
复杂度仍然没有优化,但是常数上优化了。
线性筛法(欧拉筛)
重头戏来了:利用欧拉筛,可以在线性时间内,即 $\Theta (N)$ 的复杂度筛出 1 到 N 的所有素数。
反思前面的代码,我们发现,其实很多合数被标了很多很多次,比如 $36=2\ast 18=3 \ast 12=4 \ast 9=6\ast 6$……能不能让所有素数都被筛到一次呢?
换一种思路,我们用 prime 数组记下所有素数。接下来枚举 prime 数组里的素数的倍数就可以了!
代码如下(这里我用 prime[0] 表示素数数量):
inline void BuildPrime(){
vis[1]=false;
for (int i=2;i<=N;i++){
if (vis[i]) prime[++prime[0]]=i;
for (int j=1;j<=prime[0];j++){
if (i*prime[j]>N) break;
vis[i*prime[j]]=false;
if (i%prime[j]==0) break; // 如果再往后,prime[j] 就不是 i*prime[j] 的最小质因子了,所以不需要继续了
}
}
}
关键在于 if (i%prime[j]==0) break
这句,这是欧拉筛的精髓。我们只要当前 $prime[j]$ 是 $i\ast prime[j]$ 的最小质因子,再往后就不需要做了。
November 25th, 2020 at 05:09 pm
一个建议,公开评论区,一定可以让你的博客变得更好。
November 25th, 2020 at 05:11 pm
哦哦,抱歉,网卡住了导致评论被吞?建议取消,谢谢你的这篇文章,对我的工作起到了极大的帮助。