埃氏筛法（朴素筛法及其优化）与欧拉筛（线性筛法）略解

文章目录

• 朴素筛法（埃氏筛法）
  • 时间复杂度
  • 朴素筛法的优化
• 线性筛法（欧拉筛）

在之前我们学过的最朴素的筛法就是埃氏筛法（埃拉托斯特尼筛法），它的复杂度是 $\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]$ 的最小质因子，再往后就不需要做了。