## The First N Primes

### October 14, 2011

The Sieve of Eratosthenes computes all primes less than some given *n*. But sometimes you need the opposite, the first *n* primes, not knowing the largest prime in the set. One method is to calculate the *n*th prime, using a prime-counting formula, then use the Sieve of Eratosthenes to generate the list. Or instead of calculating the *n*th prime directly, you can over-estimate the *n*th prime using the formula *P _{n}* <

*n*log (

*n*log

*n*), then trim the list as needed; that’s the natural logarithm to the base

*e*.

Another method is described by Melissa O’Neill in her article *The Genuine Sieve of Eratosthenes*. Her method is based on sifting each prime, and makes exactly the same sequence of calculations as the regular Sieve of Eratosthenes, but instead of marking bits in a bitarray it uses a priority queue to keep track of composites, one item in the priority queue for each prime; thus, instead of marking all the composite multiples of each sifting prime all at once, in the bitarray, O’Neill’s method keeps a priority queue of the next item in each sifting sequence, inserts a new sifting sequence in the priority queue as each new prime is encountered, and resets the next item in each sifting sequence as it is reached.

Thus, ignoring 2 and the even numbers, O’Neill’s method begins with *i* = 3 and an empty priority queue. Since 3 is not in the priority queue, it is prime, so it is output, the pair *i*×*i*/*i*×2 = 9/6 is added to the queue, and *i* is advanced to *i* + 2 = 5. Now since 5 is not in the queue, it is prime, so it is output, the pair 25/10 is added to the queue, and *i* is advanced to 7. Now since 7 is not in the queue, it is prime, so it is output, the pair 49/14 is added to the queue, and *i* is advanced to 9; at this point the queue is [9/6 25/10 49/7]. Now *i* = 9 *is* in the queue, so it is composite, and the pair 9/6 is removed from the priority queue and replaced by the pair 15/6, where 15 is calculated as the current composite 9 plus the skip value 6. And so on, until the desired number of primes has been generated. Note that in some cases a composite will be a member of multiple sifting sequences, and each must be replaced; for instance, when *i* reaches 45, it is a member of the sifting sequences for both 3 and 5, so the priority queue will have pairs 45/6 and 45/10, which should be replaced by 51/6 and 55/10, respectively.

Your task is to implement O’Neill’s algorithm to compute the first *n* primes. 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.