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?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ What's wrong with the ones given on the page? $\endgroup$– NoldorinCommented Jul 28, 2010 at 11:34
-
2$\begingroup$ There is only one algorithm there. And I don't think it's possible to calculate $pi(10^{23})$ using it. Also there are no bounds on it's complexity. $\endgroup$– falagarCommented Jul 28, 2010 at 11:48
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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
answered Jul 28, 2010 at 12:52
$\begingroup$
$\endgroup$
1
You can use inclusion exclusion principle to get a boost over the Eratosthenes sieve
-
$\begingroup$ I'm not sure what do you mean, but Eratosthenes sieve is way too slow for numbers like 10^23. Could you provide an asymptotic complexity of your approach? $\endgroup$– falagarCommented Jul 28, 2010 at 11:23
$\begingroup$
$\endgroup$
3
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.
-
4$\begingroup$ There is no way that $\pi(10^{23})$ could be calculated using the sieve of atkin (in any reasonable amount of time) $\endgroup$ Commented Jul 28, 2010 at 14:51
-
$\begingroup$ Right. This pages could be useful: ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/… ieeta.pt/~tos/primes.html $\endgroup$– zarCommented Jul 28, 2010 at 15:56
-
$\begingroup$ This is one of the papers linked to on Bill's page; they were able to use it calculate $\pi(10^{18})$, but more advanced refinements were needed to calculate higher than that $\endgroup$ Commented Jul 28, 2010 at 16:22