大家好我叫有兴趣的人！

看了毛爷爷的【π(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里所有表情都出现啦！）