在之前我们学过的最朴素的筛法就是埃氏筛法(埃拉托斯特尼筛法),它的复杂度是 $\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;

不得不说这个算法的确特别直观:把所有合数都筛掉。维基百科上还有个很形象的图(不得不说维基百科真是个好地方):

 title=

吐槽一句,这个筛法全名叫“埃拉托斯特尼筛法”……你知道为什么欧拉筛不叫欧氏筛法而只有这个筛法叫做埃氏筛法吗……

时间复杂度

可以看出,这个算法的计算量是 $\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]$ 的最小质因子,再往后就不需要做了。