## Counting Primes

### January 7, 2011

We celebrate our 200th exercise by implementing the prime-counting function, which has long been of interest to mathematicians. Generally denoted by the letter π, the prime-counting function π(*n*) returns the number of primes less than or equal to *n*; for instance, π(100) = 25. A related function, generally denoted as P_{n}, returns the *n*th prime number; thus, π(P_{n}) = *n*.

There are various analytic methods to compute the prime-counting function; the method invented by Ernst Meissel, improved by Derrick Henry Lehmer, and automated by Andrew Odlyzko is the best-known of them. But the obvious brute-force method of generating and counting the primes is hard to beat if you pre-compute a list of starting points, then use a segmented sieve to interpolate.

Your task is to write the prime-counting function and the nth-prime function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

This is too easy in J, which has a _primes_ operator: p:

First, define ‘n’ as the Number of Primes function: _1 p: N

n =: _1&p:

n 100

25

d,:n d=:100+i.10

100 101 102 103 104 105 106 107 108 109

25 25 26 26 27 27 27 27 28 28

p: num is the primes function, which by default returns the first primes.

The first 25 primes:

p: i.25

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

I don’t have time to do this properly today, so I’ll cheat with Haskell’s primes

package. It’s wicked fast, using “an efficient lazy wheel sieve for prime

generation.” I only tested up to 10,000, but the same code can work for 1e12

with patience and compilation. My compiler’s misbehaving today, though :-(

I wrote this one in a couple of forms a few months ago as a study in sieving. It’s not really pretty (nothing using pthreads is) but it chugs along pretty well. I can count all the primes up to 10^10 in about 12 seconds of elapsed time on my 8 processor machine, and it takes somewhere around 20 minutes to do all the way up to 10^12. There are actually ways to count primes that don’t involve finding all the primes, but they seemed impractical (hard to understand, and therefore hard to write).

[...] weekÂ Programming Praxis proposed to write two [...]