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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|||||||||
|
|
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 http://primes.utm.edu/howmany.shtml |
|||
|
|
|
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). (edit) I found a distributed computation project which was able to calculate $pi(4\times 10^{22})$, maybe it could be useful. |
|||||||||
|
