Counting primes

Let $\pi(x)$ be the number of primes not greater than $x$.

Wikipedia article says that $\pi(10^{23}) = 1,925,320,391,606,803,968,923$.

The question is how to calculate $\pi(x)$ for large $x$ in a reasonable time? What algorithms do exist for that?

Solutions Collecting From Web of "Counting primes"

The most efficient prime counting algorithms currently known are all essentially optimizations of the method developed by Meissel in 1870, e.g. see the discussion here

You can use inclusion exclusion principle to get a boost over the Eratosthenes sieve

The Sieve of Atkin is one of the fastest algorithm used to calculate $pi(x)$. The Wikipedia page says that its complexity is O(N/ log log N).


I found a distributed computation project which was able to calculate $pi(4\times 10^{22})$, maybe it could be useful.