超越欧拉的质数筛法

本算法最初由 @[wangchenyi](/user/631814) 发明，时间复杂度为 $O(\dfrac{n}{\log_2n})$，常数巨大，大约 $100$ 倍常数。[原帖在这](/discuss/839771)，我帮他做了格式上的优化。 ## 算法思路和时间复杂度证明 以下方便起见，令 $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})$，我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大），证毕。