很多人都知道埃氏筛法的时间复杂度是\(O(n \lg\lg n)\)，但同样有很多人不知道这个结果是怎么来的。我有一种非常非常不严谨，然而相当简单的方法，可以得到正确的结果。可惜不知道它是否仅仅是歪打正着。。。
定义\(\pi(n)\)为前\(n\)个自然数中素数的数量。关于\(\pi\)函数，数论中有个著名结果：
\[\lim_{n\to \infty}\frac{\pi(n)}{\frac{n}{\ln n}}=1
\]
所以我们在这里就非正式地令\(\pi(n)=\frac{n}{\ln n}\)了。
所以由微积分基本定理，左开右闭区间\((a,b]\)中的素数数量大概就是：
\[\begin{align}
\pi(b)-\pi(a)&=\int_{a}^{b}\frac{\mathrm{d} }{\mathrm{d} x} \left ( \frac{x}{\ln x} \right )\mathrm{d} x \notag\\
&=\int_{a}^{b}\frac{\ln x - 1}{\ln^2 x} \mathrm{d} x \notag
\end{align}
\]
用素数\(x\)筛去\(x\)的倍数的消耗大约是\(\frac{n}{x}\)。
假设素数是完全随机出现的，则整数\(x\)是素数的概率为：
\[\begin{align}
P(x\text{ is prime})&=\pi(x)-\pi(x-1)\notag\\
&=\int_{x-1}^{x}\frac{\ln t - 1}{\ln^2 t} \mathrm{d} t \notag
\end{align}
\]
筛去\(x\)的期望代价是：
\[\begin{align}
P(x\text{ is prime})\cdot \frac{n}{x}&=\frac{n}{x}\left(\pi(x)-\pi(x-1)\right)\notag\\
&=n\int_{x-1}^{x}\frac{\ln t - 1}{x\ln^2 t} \mathrm{d} t \notag\\
&\approx n\int_{x-1}^{x}\frac{\ln t - 1}{t\ln^2 t} \mathrm{d} t \notag\\
&= n\int_{x-1}^{x}\frac{\ln t - 1}{\ln^2 t} \mathrm{d} (\ln t) \notag
\end{align}
\]
所以筛去所有数的总代价为：
\[\begin{align}
&\:\;\;\;\;\sum_{x=2}^{n}n\int_{x-1}^{x}\frac{\ln t - 1}{\ln^2 t} \mathrm{d} (\ln t)\notag\\
&=n\int_{1}^{n}\frac{\ln t - 1}{\ln^2 t} \mathrm{d} (\ln t)\notag\\
&=n\int_{e}^{\ln n}\frac{t - 1}{t^2} \mathrm{d} t\notag\\
&=n\left (\ln t+\frac{1}{t}\right )\Bigg|^{\ln n}_e\notag\\
&=O(n\lg \lg n)\notag
\end{align}
\]
\(Q.E.D.\)