# The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?

• removed tags for loop theory (not what you're thinking of, its a totally different abstract realm of mathematics), added appropriate tags for relevant subjects – frogeyedpeas Aug 7 '14 at 5:01
• Have you tried the sieve of Erathostenes? – Per Manne Aug 7 '14 at 5:02
• See also the Prime-counting function (also here) – Jean-Claude Arbaut Aug 7 '14 at 5:06
• Do you want an exact count or an approximate value is fine? – Yashbhatt Aug 7 '14 at 11:08

Some methods:

• Count via primality as mentioned by frogeyedpeas. Use something like BPSW since we're not going to be over $2^{64}$. Lowest memory, but crazy slow and using a segment sieve makes the memory issue pretty much moot. An additional note since it was brought up, AKS is completely impractical to use for this -- it provides no benefit and runs extremely slow.

• Use a segmented sieve. primesieve is an excellent off-the-shelf choice, but you can find them all over. Segmenting the SoE will result in both faster performance for large inputs as well as constraining the memory to whatever sane bound you want. It loses steam around $10^{11}$ or so, and isn't the fastest method regardless.

• Use a sparse table plus a segmented sieve. This can be quite fast, as the sparse table holds the counts at selected intervals, meaning you only need to sieve from the closest table point. Mathematically no more interesting than the previous option, but in practice this helps. I use this for numbers under 60,000,000, as that was the crossover for my code when looking at optimizing performance while keeping the table space under 2k.

• Combinatorial prime count methods. These include the Legendre, Meissel, Lehmer, LMO, and LMO extensions. See code for each at primecount or Math::Prime::Util. These are much, much faster than sieving. A single core can count in a second what primesieve (the current fastest sieve code) takes over 2 hours to do using 8 cores. The growth rate is lower as well so this difference just gets bigger. Memory growth for Legendre/Meissel/Lehmer can be problematic for very large values, but LMO and eLMO are quite good up to $2^{64}$. References include:

• Analytic methods, introduced in 1987 by Lagarias and Odlyzko in Computing $\pi(x)$: An Analytic Method. See, for example, How to Not Count Primes, a little presentation by DJ Platt. The analytic methods have been used for values up to $10^{25}$, and for years were about two orders of magnitude higher than the combinatorial methods. I'm not aware of any open source implementations, but two research teams are actively working on running their implementations (FKBJ and Platt).

5 months after I originally wrote this, Douglas Staple published his results for $10^{26}$ from a distributed combinatorial algorithm. Later Kim Walisch wrote a distributed version his excellent open source primecount program, which was used to validate the result. Continuous improvements have been made to his program, and it currently holds the record for calculating $\pi(10^{27})$. It is also the fastest program for smaller numbers as well.

Note that approximations and bounds can be done very quickly and are extremely close. For bounds see Dusart (2010). This is actually an area of current research, with papers showing tighter bounds coming out every year. For approximation we can use the simple $n/(log(n)-1)$ which works but much worse than the following methods. Averaging the Dusart bounds gets significantly closer without a lot more work. The Logarithmic Integral is much closer yet. We can improve on this by adding another term: $\pi(n) \approx li(n)-li(\sqrt{n})/2$. Better yet is the full Riemann R function. It is off by only 0.00000001% at $10^{19}$.

• Simple timings, count how far in 1 second: $1\times 10^7$ primality; $5\times 10^8$ sieve; $1\times 10^{12}$ Legendre; $2\times 10^{12}$ Meissel; $3\times 10^{12}$ Lehmer; $8\times 10^{13}$ LMO – DanaJ Aug 11 '14 at 8:38

So I think @Per Manne's comment deserves attention

The Sieve of Eratosthenes is one of the faster ways of counting primes numbers (most advanced methods are really just the Sieve of Eratosthenes with additional optimizations) but it takes time and space proportional to the size of the number being evaluated

Algorithm for Sieve of Eratosthenes,

Initialize array of odd numbers from 2 to N (I say odd since we know no even greater than 2 works, you can always get fancier and say instead of just odds we will consider odd numbers that aren't divisible by 3, or odd numbers not diviisble by 3 or 5 etc... to save space here, notice how I am just sort of pre-running the sieve)

Sieve(array, k): If(k > size of array): return array: else: take the k'th element of the array and check all greater elements if divisible by k, for each greater element that is divisible remove it*. Next run Sieve(array, k+1).

*(one can get fancier by knowing how to pick elements (there are patterns! although subtle) so not all elements are checked)

For extremely large N (I mean n that takes megabytes just to store) to list out all these numbers is not practical.

In that case a different choice of algorithm which still takes time proportional to the size of the number, but space that isn't proportional to the size of the number can be implemented

This algorithm is really simple (in an abstract view):

Create a value x (Set it at 2) Create a value counter (keeps track of # of primes) Run a deterministic primality test on x, if x is prime up the counter. Increment x by 1. Run until x = N

Now of course in incrementing x we can get fancy and only pick odd numbers (increment x by 2) or get even fancier and dodge the multiples of 3 etc... that again is all surface level optimization.

Now this method still requires you to go through all the numbers up to N however it doesn't need to have all the numbers listed out! Examples of deterministing primality tests are:

http://en.wikipedia.org/wiki/AKS_primality_test

Hope that helps!

• If anything the second method is slower, but it has a MUCH smaller space constraint – frogeyedpeas Aug 7 '14 at 5:23

A relative fast and easy way is the Legendre-Meissel-Lehmer method basically described at the Algorithms section of the link already given by @Jean-Claude Arbaut.

More mathematical background and improvements can be found in the article by Tomás Oliveira e Silva 'Computing $\pi(x)$: the combinatorial method' (available from his page as http://sweet.ua.pt/tos/bib/5.4.pdf). It even contains example C code for the Legendre function.

A more complete C implementation of this method is the code from Dana Jacobsen given in external link section of the Wiki article.

If you just want an approximation then you can use the Prime Number Theorem. I myself don't know much about the theorem. But I watched a video on Khan Academy about it. It states that if we plot the no. of primes smaller than a given number $n$ then the graph resembles the graph of $y = {x}/ ln(x)$. As $x \longrightarrow \infty$, the value gets nearer to the actual number of primes. See this video for more information.

• Using the average of the Dusart (2010) upper/lower bounds is almost as easy and a couple orders of magnitude closer. The Logarithmic Integral is much closer, and Riemann's R function is closer yet (off by only 0.00000001% at $10^{19}$). They're more complicated to program however, though many libraries have them, e.g. Mathematica, Wolfram Alpha, Pari/GP, Perl's MPU, Python's mpmath, MPFR for C, ... – DanaJ Aug 11 '14 at 7:16