论文标题
计算$π（n）$：$ \ tilde {o}（\ sqrt {n}）$ time中的基本方法
Computing $π(N)$: An elementary approach in $\tilde{O}(\sqrt{N})$ time
论文作者
论文摘要
我们提出了一种高效且基本的算法，用于计算$ \ tilde {o}（\ sqrt n）$时间最多$ n $的数量，从而改善了需要$ \ tilde {o}的现有组合方法（n ^ {2/3}）$时间。我们的方法具有与分析方法相似的时间复杂性，同时避免了复杂的分析和使用任意精度复数。虽然我们算法的最耗时的版本需要$ \ tilde {o}（\ sqrt n）$ space，但我们提出了一个连续的时空折衷，例如，例如，如何将空间复杂性降低到$ \ tilde {o}（o}（o}（\ sqrt [3] {3] {n}）$， $ \ tilde {o}（n^{8/15}）$。我们应用技术来改善用于计算其他数字理论功能的基本算法的最新复杂性，例如Mertens函数（在$ \ tilde {o}中（\ sqrt n）$时间，与已知的$ \ tilde {o}（o}（o}（o）相比提供了实施代码。
We present an efficient and elementary algorithm for computing the number of primes up to $N$ in $\tilde{O}(\sqrt N)$ time, improving upon the existing combinatorial methods that require $\tilde{O}(N ^ {2/3})$ time. Our method has a similar time complexity to the analytical approach to prime counting, while avoiding complex analysis and the use of arbitrary precision complex numbers. While the most time-efficient version of our algorithm requires $\tilde{O}(\sqrt N)$ space, we present a continuous space-time trade-off, showing, e.g., how to reduce the space complexity to $\tilde{O}(\sqrt[3]{N})$ while slightly increasing the time complexity to $\tilde{O}(N^{8/15})$. We apply our techniques to improve the state-of-the-art complexity of elementary algorithms for computing other number-theoretic functions, such as the the Mertens function (in $\tilde{O}(\sqrt N)$ time compared to the known $\tilde{O}(N^{0.6})$), summing Euler's totient function, counting square-free numbers and summing primes. Implementation code is provided.
