目录

目录地址

质数的朴素筛法

根据定义，我们不难得出，如果要知道 \(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(n\sqrt n)\) 的

其实，本人对此持怀疑态度：本人认为只有 \(o(n\sqrt n)\)

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

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

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

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

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

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

优化

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

所以，我们把之前筛到的所有质数存起来，依次判断是不是这个数的因数就行了

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

因为 \(1\)~\(n\) 的质数个数约等于 \(n\over\ln n\) （我们假定特殊化处理：\(\ln 1=1\)）

所以复杂度为 \(\displaystyle T(n)=\sum_{i=1}^n {\sqrt{i}\over \ln \sqrt{i}}=2\sum_{i=1}^n{\sqrt{i}\over \ln i}\)

可以证明，复杂度 \(T(n)\) 与变上限函数 \(\displaystyle \int_a^n {\sqrt{i}\over\ln i}\text di\) 是同阶的

不过很可惜，这玩意儿的积分我不会，不过我们可以发现：当 \(n\) 足够大时，一定会满足下面不等式：

\({\text d\over \text di}(i\ln\ln i)=\ln\ln i+{1\over \ln i}\leq {\sqrt i\over \ln i}\leq \ln i+1= {\text d\over \text di}(i\ln i)\leq {3\over 2}\sqrt i={\text d\over \text di}(i\sqrt i)\)

因此 \(\displaystyle n\ln\ln n\leq \int_a^n{\sqrt i\over \ln i}\text di\leq n\ln n\leq n\sqrt n\)

所以，我们可以说，这个方法肯定是更优的，复杂度是 \(o(n\log n)\) 的，但因为同时也是 \(\omega(n\log\log 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<=n;j+=i){
        isntprime[j]=1;
    }
}

有人认为这个复杂度的计算是 \(\displaystyle T(n)=\lfloor{n\over 1}\rfloor+\lfloor{n\over 2}\rfloor+\lfloor{n\over 3}\rfloor+\cdots+\lfloor{n\over n}\rfloor\approx{n\over 1}+{n\over 2}+{n\over 3}+\cdots+{n\over n}=n\sum_{i=1}^n{1\over i}=n(\ln n+\gamma)\) ，得出复杂度 \(O(n\log n)\) 的结论

其实这个估计偏大了：

\(1\)~\(n\) 以内的质数个数大概是 \({n\over \ln n}\) 个，第 \(i\) 个质数 \(p_i\approx i\ln i\)（同样，为了方便，我们定义此处 \(\ln 1=1\)）

因此，复杂度实际为 \(\displaystyle T(n)\approx\sum_{i=1}^{n\over\ln n}\lfloor{n\over p_i}\rfloor\approx\sum_{i=1}^{n\over\ln n}\lfloor{n\over i\ln i}\rfloor\approx n\sum_{i=1}^{n\over \ln n}{1\over i\ln i}\)

可证明得 \(\displaystyle \sum_{i=1}^n{1\over i\ln i}\) 的复杂度与变上限函数 \(\displaystyle \int_a^n{1\over i\ln i}\text di\) 相同

由 \(\displaystyle \int_a^n{1\over i\ln i}\text di=(\ln\ln i)|_a^n=\ln\ln n-\ln\ln a\) 得到

我们把常数都归为 \(C\)

因此 \(\displaystyle T(n)\approx n\sum_{i=1}^{n\over \ln n}{1\over i\ln i}=n(\ln\ln{n\over \ln n}-C)=n\ln\ln n-n\ln\ln\ln n-nC\)

故复杂度应为 \(O(n\log\log n)\)

优化

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

比如 \(6=2\times 3\)，就被 \(2\) 与 \(3\) 各筛了一次，这就导致了为什么复杂度是 \(O(n\log\log 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;
    }
}

我们重新计算一下时间复杂度：对于大于 \(\sqrt n\) 的质数已经对复杂度没有了贡献，因此：

\(\displaystyle T(n)\approx\sum_{i=1}^{\sqrt n\over\ln \sqrt n}\lfloor{n-p^2\over p}\rfloor\approx n\sum_{i=1}^{2\sqrt n\over \ln n}{1\over p}-\sum_{i=1}^{2\sqrt n\over \ln n}p\)

前半部分 \(\displaystyle n\sum_{i=1}^{2\sqrt n\over \ln n}{1\over p}=n\sum_{i=1}^{2\sqrt n\over \ln n}{1\over i\ln i}=n\ln\ln{2\sqrt n\over \ln n}+C\) 复杂度为 \(O(n\log\log n)\)

后半部分 \(\displaystyle \sum_{i=1}^{2\sqrt n\over \ln n}p\approx\sum_{i=1}^{2\sqrt n\over \ln n}i\ln i\)

同样可证明， \(\displaystyle \sum_{i=1}^ni\ln i\) 复杂度同变上限函数 \(\displaystyle \int_a^ni\ln i\text di\) 同阶

由 \(\displaystyle \int_a^ni\ln i\text di=({1\over 2}i^2\ln i-{1\over 4}i^2)|_a^n\)

常数归为 \(C\) ，积分值为 \({1\over 2}n^2\ln n-{1\over 4}n^2+C\)

因此后半部分复杂度 \(T(n)={1\over 2}({2\sqrt n\over \ln n})^2\ln n-{1\over 4}({2\sqrt n\over \ln n})^2+C\) 为 \(O({n\over \log n})\)

因此，总时间复杂度为 \(O(n\log\log n)-O({n\over\log n})=O(n\log\log n)\)

可以理解为常数更小

质数的两种筛法

原文：https://www.cnblogs.com/JustinRochester/p/12335779.html