超越欧拉的质数筛法

对原文中的错误致歉

原文：

$$m+w=O(n*π_{i=1}^m(1-\frac{1}{p_i}))$$

实际上是

$$m+w=O(n*π_{i=1}^c(1-\frac{1}{p_i}))$$

所以时间复杂度应为从$O(\frac{n}{loglogn})$到$O(\frac{n}{logn})$①
仍然超越欧拉，但是并不是确定机的时间复杂度

但相比于Miller_Robin算法，这是一个确定的算法，还是有意义的

我们还是证明一下①

与原文类似的，

$$\begin{aligned} -lnT&=\sum_{i=1}^c\sum_{k=1}^{+oo}\frac{1}{kp_i^k}\\&=\sum_{i=1}^c\frac{1}{p_i}+\theta_n\\&>=loglogc-2 \end{aligned}$$

故

$$T<=\frac{e^2}{logc}$$

下面估计c

显然，c<n

下证$c>ln n$

显然$p_i>i^2$

故

$$\begin{aligned} n&<π_{i=1}^{c+1}p_{i+1}\\&<π_{i=1}^{c+1}{(i+1)^2}\\&=((c+1)!)^2 \end{aligned}$$

由stiriling公式知:

$(c+1!)=(2π(c+1))^{\frac{1}{2}}(\frac{c}{e})^c(1+O(\frac{1}{n}))$

代回可知（以下部分等号按等价号理解）

$$\begin{aligned} n&<((c+1)!)^2\\&<(2π(c+1))(\frac{c}{e})^{2c}(1+O(\frac{1}{n})) \end{aligned}$$

可以推出:$clogc>\frac{1}{4}n$

故$c>logn$

故时间复杂度应为从$O(\frac{n}{loglogn})$到$O(\frac{n}{logn})$
仍然超越欧拉，但是并不是确定机的时间复杂度

声明：本文和原文中的log均以e为底