质数的两种筛法

质数的朴素筛法：(O({nsqrt nover log n}))

根据定义，我们不难得出，如果要知道 (1)~(n) 范围内的所有质数，我们只需要从 (2) 到 (n) 开始枚举，再判断是否是质数即可：

bool isprime[MAXN];
for(int i=2;i<=n;i++){
    isprime[i]=1;
    for(int j=2;j*j<=i;j++){
        if(i%j==0){
            isprime[i]=0;
            break;
        }
    }
}

当枚举到的数为 (n) 的时候，内层的复杂度是 (O(sqrt n)) 的，而外层 (O(n)) 枚举

因此，很多人觉得是 (O(nsqrt n)) 的

其实，本人对此持怀疑态度

首先：每个合数都是被自己的最小质因子筛到，而每个质数 (p) 花费的时间是 (O(sqrt p))

质数的很显然，对于合数的，我们用反证法：如果这个数 (m) 的最小质因数为 (fc) ，它被判定为合数时 (i=k)

因此， (m) 应该在 (k) 之前都不能退出循环

而如果 (fc) 为 (k) 的因数，(fc<k)(因为 (k) 为合数)；如果不为的话， (k) 的最小质因数假设为 (fc') 则 (fc<fc'<k)

因此， (m) 在 (fc) 时就一定退出了

综上，复杂度其实并没有达到 (O(nsqrt n)) ，其实复杂度是更小的

经本人不严谨证明复杂度大概为 (O({n^{3over 2}over log n}))

优化 (o({n^{3over 2}over log n}))

我们考虑每个合数，一定是被它的最小质因数筛到。而一个数 (n) 的最小质因数 (fc) ，一定有 (fcin Prime,fcleq n)

所以，我们把之前筛到的所有质数存起来，筛到 (n) 时，依次枚举不大于 (sqrt n) 的质数判断是不是这个数的因数就行了

bool isprime[MAXN];
int prime[MAXN],cntprime=0;
for(int i=3;i<=n;i++){
    isprime[i]=1;
    for(int j=1;prime[j]*prime[j]<=i&&j<=cntprime;j++){
        if(i%prime[j]==0){
            isprime[i]=0;
            break;
        }
    }
    if(isprime[i]==1){
        prime[++cntprime]=i;
    }
}

枚举质数的速度比优化前更快。优化前枚举到第 (t) 个质数 (p_t) 的开销是 (O(p_t)) ，优化后是 (O(t)) 。

埃氏筛 (O(nloglog n))

埃拉托斯特尼（Eratosthenes）筛法，简称埃氏筛，由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

显然，对于某个质数 (p) ，它的倍数（除了它本身）一定不是质数

因此，我们把每枚举一个质数 (p) ，就把它的这些倍数全部打上不是质数的标记

bool isntprime[MAXN]={0};
for(int i=2;i<=n;i++){
    if(isntprime[i]==1) continue;
    for(int j=i+i;i<=n;j+=i){
        isntprime[j]=1;
    }
}

有人认为这个复杂度的计算是 (displaystyle T(n)=lfloor{nover 1} floor+lfloor{nover 2} floor+lfloor{nover 3} floor+cdots+lfloor{nover n} floorapprox{nover 1}+{nover 2}+{nover 3}+cdots+{nover n}=nsum_{i=1}^n{1over i}=n(ln n+gamma)) ，得出复杂度 (O(nlog n)) 的结论

其实这个估计偏大了：

同样身经本人不严谨证明，复杂度应为 (O(nloglog n))

优化 (O(nloglog n))

我们可以发现，每个数字实际上被它的所有质因数都筛了一遍：

比如 (6=2 imes 3)，就被 (2) 与 (3) 各筛了一次，这就导致了为什么复杂度是 (O(nloglog n)) 而不是 (O(n))

我们考虑到，对任意质数 (p) ，以它为最小质因数的数字最小为 (p^2)

所以我们换一个枚举下界：从 (p^2) 开始枚举即可

bool isntprime[MAXN]={0};
for(int i=2;i<=n;i++){
    if(isntprime[i]==1) continue;
    for(int j=i*i;i<=n;j+=i){
        isntprime[j]=1;
    }
}

我们重新计算一下时间复杂度，可以发现，时间复杂度不变，但常数更小

线性筛 (O(n))

欧拉（Euler）筛法，简称欧式筛，或因为其线性复杂度被称呼为线性筛。由瑞士数学家欧拉提出

它在埃氏筛的基础上，用一个方法，限定了每个数只被其最小质因数 (fc) 筛到一次，从而保证时间复杂度为 (O(n))

思想比较巧妙：

对于当前数字 (n) ，假设它的最小质因数为 (fc)

对于已经筛出的质数，存在表 prime 中

那么，我们从质数表中，枚举最小质因数不大于 (fc) 的质数 (p)

我们就能保证： (p imes n) 的最小质因数一定为 (p)

那么，事先没被标记最小质因数的数字就一定是质数，且最小质因数为它本身

代码实现如下：

int fc[MAXN]={0},prime[MAXN],cntprime=0;
for(int i=2;i<=n;i++){
    if(fc[i]==0){
        fc[i]=i;
        prime[++cntprime]=1;
    }
    for(int j=1;j<=cntprime&&prime[j]<=fc[i]&&prime[j]*i<=n;j++){
        fc[i*prime[j]]=prime[j];
    }
}

这个代码推荐背住，对后期的简单积性函数也可以使用该筛法，实现线性时间内求出

STL-版