埃式筛法代码如下:
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
参考内容:
- - - 结束 - - -
漂亮的推导。
Mertens therorem 有中文资料吗?我没有找到,甚至不知道Mertens中文叫什么
中文叫梅尔滕斯定理,中文资料俺也没找到 ::aru:dead::