Counting primes

$\begingroup$

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?

$\endgroup$ 2

3 Answers

$\begingroup$

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

$\endgroup$ $\begingroup$

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

$\endgroup$ 1 $\begingroup$

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).

(edit)

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

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy