埃式筛法代码如下:

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

参考内容

Last modification:February 19th, 2020 at 04:32 pm
如果觉得我的文章对你有用,请随意赞赏~