大家好我叫有兴趣的人！
看了毛爷爷的【π(n)的计算】之后，我直接被吓傻了
然而，在看了【帅气的算法二】之后，我发现了一个不优美的地方！
就是那个$P_k(x,n)$的计算复杂度和$\Phi(x,n)$的计算复杂度不一样！
这怎么能忍！！！
其实我们可以做到$O(x^\frac34)$
我们把$y$取成一个$x^{\frac14}$左右的数
这样，$\Phi(x,n)$的计算降低到了$O(x^\frac34)$
同时$P_k(x,n)$由于涉及到最大到$\frac xy$的$\pi$值，所以需要筛出$O(x^\frac34)$的质数
总共加起来的复杂度还是$O(x^\frac34)$的!
一个小bug
Wait!
这里有个问题！
由于$y$减小了$P_3(x,n)$不再是0了!
怎么办呢？
其实可以直接暴力的！
$P_3(x,n)$的意思是小于$x$的数中，可以表示为$3$个大于$p_n$的质数之积的个数。
我们枚举第一小和第二小的质数，会发现一个不超过$x^\frac13$，一个不超过$x^\frac38$，总共只有$x^\frac{17}{24}$，比$x^\frac34$少了$x^\frac1{24}$呢!
这样就完美解决啦！
经过修改的算法比原来的$n^\frac56$相比，在$x=10^9$的时候，从$329\texttt{ms}$ 缩短到了$94\texttt{ms}$(vfk教导我们单位要用等宽字体)!
$x=10^{10}$也可以1秒出解啦！
（其实这篇blog里所有表情都出现啦！）
鄂公网安备 42010202000505 号