MENU

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

February 14, 2020 • Read: 1114 • 编程之路,Algorithm

埃式筛法代码如下:

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下载

- - - 结束 - - -
  • 文章标题:为什么埃式筛法的时间复杂度是O(nloglogN)?
  • 文章链接:https://blog.canye365.cn/archives/197.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: February 8, 2021
    Leave a Comment

    2 Comments
    1. yumeko yumeko   Android 9(Android 9) / Google Chrome 57.0.2987.108(Google Chrome 57.0.2987.108)

      漂亮的推导。
      Mertens therorem 有中文资料吗?我没有找到,甚至不知道Mertens中文叫什么

      1. 残夜 残夜   Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 69.0.3497.100(Google Chrome 69.0.3497.100)

        @yumeko中文叫梅尔滕斯定理,中文资料俺也没找到 ::aru:dead::