我写这篇文章的灵感其实来自于我在洛谷上做的一道题P3383。

都8102年了我还在用我2015年学的埃拉托斯特尼筛法

咳咳，不扯别的了，今天我们来聊一聊一个跑的更快的求质数的算法——欧拉筛法。

首先介绍一下欧拉筛法的原理

任何一个合数都可以表示成一个质数和一个数的乘积

$$ A = x * y (y是质数A,x是合数且y>x)$$

$$ x = a * b(a<x,a<y)$$

$$A = a b y \rightarrow A = aZ(Z = b * y)$$

也就是比一个合数大的质数和该合数的乘积可用一个更大的合数和更小的质数相乘得到。

放一下代码

for(int i=2;i<=n;++i) {
        if(!nonprime[i]) //非质数表
            prime[++tot] = i;

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

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

这也就是真正的所谓线性筛法了。

更神奇的是还有dalao举出了米勒-拉宾素性检验这个神奇的东西，这里就不讨论了。

参考资料：

• 洛谷P3383题解区