English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present an efficient and elementary algorithm for computing the number ofprimes up to $N$ in $\tilde{O}(\sqrt N)$ time, improving upon the existingcombinatorial methods that require $\tilde{O}(N ^ {2/3})$ time. Our method hasa similar time complexity to the analytical approach to prime counting, whileavoiding 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})$. Weapply our techniques to improve the state-of-the-art complexity of elementaryalgorithms for computing other number-theoretic functions, such as the theMertens function (in $\tilde{O}(\sqrt N)$ time compared to the known$\tilde{O}(N^{0.6})$), summing Euler's totient function, counting square-freenumbers and summing primes. Implementation code is provided.

Computing $\pi(N)$: An elementary approach in $\tilde{O}(\sqrt{N})$ time