以下方便起见,令 p 为质数序列($p_1=2, p_2=3,\dots$),$m(n)$ 为小于 n 的质数个数,$w(n)$ 为小于 n 的非完全合数。
本算法主要是通过递推跳过“完全合数”。完全合数和非完全合数定义如下: 对一个合数 $n$,令 c = c(n) 为最大的整数使 $\prod\limits_{i=1}^cp_i<n$,若存在 $k(1\le k\le c)$,使 $p_k\mid n$,则称 n 为完全合数,否则为不完全合数。
由代码中的递推找到所有质数和非完全合数只需 $O(m + w)(请注意 \displaystyle \sum\limits_{k=1}^\infty\prod\limits_{i=1}^k\dfrac{1}{p_i}<\sum\limits_{k=1}^\infty\dfrac{1}{k(k-1)}=2$)。而之后我们可以通过 O(w) 的时间复杂度来找到所有非完全合数,再用 O(\sqrt{n}+w) 的时间复杂度来排序,然后是 O(m + w) 的输出。
现在此算法时间复杂度为 $O(m + w + \sqrt{n}) = O(\dfrac{n}{\log_2n} = O(m))$,故时间复杂度为 $O(m + w)$。
下证:$\lim\limits_{n\to\infty}m+w=\dfrac{n}{\log_2n}$。
(以下等于号 = 按等价理解)
由定义,$\displaystyle m + w = n \times \prod\limits_{i=1}^m(1-\dfrac{1}{p_i})$。
令 $\displaystyle T = T(n) = \prod\limits_{i=1}^m(1-\dfrac{1}{p_i})$,我们证明 $T < \dfrac{e^2}{\log_2n}: \log_2T = \displaystyle \sum\limits_{i=1}^m\log_2(1-dfrac{1}{p_i}),由 \log_2(1-x)$ 的解析性,知它的泰勒级数收敛于它本身,故:
$$\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\
&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}
\end{aligned}$$
我们估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k} 的量级,显然,对于任意的 $k\ge2$,
$$\begin{aligned}
\sum\limits_{i=1}^m&\le\sum\limits_{i=2}^{m+1}\dfrac{1}{i}\
&<\int_1^{m+1}\dfrac{1}{x^k}\mathrm dx\
&=\dfrac{1}{k-1}(1-\dfrac{1}{(m+1)^{k-1}})\
&<\dfrac{1}{k-1}
\end{aligned}$$
故
$$\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\
&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\
&<\sum\limits_{i=1}^m\dfrac{1}{p_i}+1
\end{aligned}$$
即
$$\begin{aligned}\log_2T&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\
&=\sum\limits_{i=1}^m\dfrac{1}{p_i^k}+\theta_n(0<\theta_n<1)
\end{aligned}$$
我们只需估计 $\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i},由熟知结论,\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}>\log_2\log_2n-1$,故 $\log_2T<\log_2\log_2n+2$,即 $T<\dfrac{e^2}{\log_2n}$,故 $O(m + w) = O(Tn) = O(\dfrac{n}{\log_2n})$,我们证明了此算法的时间复杂度绝不可能改进,后人只能优化常数(是的,常数非常大),证毕。