Take the 2-minute tour ×
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.

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?

share|improve this question
3  
What's wrong with the ones given on the page? –  Noldorin Jul 28 '10 at 11:34
2  
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. –  falagar Jul 28 '10 at 11:48

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer

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.

share|improve this answer
4  
There is no way that $\pi(10^{23})$ could be calculated using the sieve of atkin (in any reasonable amount of time) –  BlueRaja - Danny Pflughoeft Jul 28 '10 at 14:51
    
Right. This pages could be useful: ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/… ieeta.pt/~tos/primes.html –  zar Jul 28 '10 at 15:56
    
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 –  BlueRaja - Danny Pflughoeft Jul 28 '10 at 16:22

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

share|improve this answer
    
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? –  falagar Jul 28 '10 at 11:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.