為什麼埃式篩法的時間複雜度是O(nloglogn)？

01-08

我的想法是當n增大的時候，我們可以認為素數是近似隨機分布的，那麼時間複雜度就是n(1/(lnn)+1/(2lnn)+……+1/((n/lnn)lnn))=(n/lnn)(1/1+1/2+……+1/(n/lnn))=n*ln(n/lnn)/lnn=n*(1-lnlnn/lnn)≈n。所以應該是O(n)的呀，但為什麼是O(nloglogn)的呢？我上述分析有什麼錯誤之處么？

以下 $ple n$ 均表示所有小於等於 $n$ 的質數。

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

以這段代碼為例，時間複雜度顯然為 $T(n)=sum_{ple n}^{}{frac{n}{p} }=nsum_{ple n}^{}{frac{1}{p} }$

根據Mertens" theorems， $lim_{n ightarrow infty}{(sum_{ple n}^{}{frac{1}{p} }-ln ln n-M)}=0$ ， $Mapprox 0.2614972$ ，所以上述演算法的時間複雜度為 $O(nloglog n)$ 。

證明在此，我是一個搬運工，http://arxiv.org/pdf/math/0504289。（看了半天沒看懂捂臉逃……

思路是用素數分布定理列出表達式，然後定積分確定時間界。

如果懶得推可以移步http://m.blog.csdn.net/article/details?id=53861367