# 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?

-

3
What's wrong with the ones given on the page? – Noldorin Jul 28 '10 at 11:34

1
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

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

-

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.

-

3
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

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9213634133338928, "perplexity_flag": "head"}