为什么埃式筛法的时间复杂度是O(nloglogN)？

埃式筛法代码如下：

for(int i=2;i<=n;i++)
    if(primes[i])
        for(int j=2;j<=n/i;j++)
            prime[i*j] = false;

分析如下：

只有当$i$为质数，即$primes[i] == true$时，内层循环才执行，当执行内层循环时，循环的执行次数是$n/i$。

即循环的总次数为：

$$ \frac n 2 + \frac n 3 + \frac n 5 +... + \frac n k, (k是\le n范围内最大质数。) \\ \Downarrow \\ \sum_{p\le n} {\frac n p} = n \sum_{p\le n} {\frac 1 p} $$

根据$Mertens' theorems$

$$ \lim_{n \to +\infty} (\sum_{p\le n} {\frac 1 p} - \ln\ln n - M) = 0, M \approx 0.26 $$

得出：

$$ n\sum_{p\le n} {\frac 1 p} = n(\ln\ln n + M) = O(n\ln\ln n) = O(n\log\log n) $$

• M是Meissel-Mertens常数，$M\approx 0.2614972128$
• 严格来说$O(n\ln\ln n) \le O(n\log\log n)$, 所以可以将前者转化成后者。

---

参考文献：Villarino, Mark B, Mertens' Proof of Mertens' Theorem

参考内容：

参考文献PDF下载