Prime Generator Algorithm

The prime generator program simply generates prime numbers until you get bored and stop it (likely), the maximum integer size is reached (unlikely), or the program runs out of memory (much more likely than the last one). It is based on the sieve method, and is quite fast.

To present the algorithm used by pgen, we will start with the simple-minded prime generation method. It is based on a double loop like this: this:


Now, we will try to improve the efficiency. First, we observe that the inner loop needs only to check the d values which are themselves prime. Since it has already identified these values, we need only remember them. So now we have:



This version is faster because the inner loop performs fewer iterations. It is possible to make it still faster, however, by using a better data structure for primes. For this, first off, we observe that any given prime number eliminates a series of its multiples in increasing order. For instance, as n increases, the prime number 2 will eliminate 4, 6, 8, 10, . . ., in that order. The prime number 7 eliminates 14, 21, 28, and so forth. This means that, for any prime, we can predict which n value will be eliminated next. This leads to the notion of an eliminator object. It is a pair of numbers, a prime and one of its multiples. The multiple is the next n value which it will eliminate. It also has a method advance which moves it to its next victim. That simply means adding the prime to the multiple to create the next multiple. We keep a collection of these. For each n value, we check to see if a member of our eliminator collection eliminates n. If so, we know that that n is not prime, and we advance the eliminator. The algorithm becomes:



Here's what that looks like:

Finally, we want to answer the question "if eliminators contains some eliminator e = (p, eliminators)" quickly. First observe that, at each step, if there is an eliminator for n in eliminators, it is always one with the smallest multiple. Therefore we organize eliminators as a heap. A heap is a data structure from which is it is efficient to find the smallest (or largest) item.

I use the vector class from the C++ standard libraries to hold eliminators. The standard libraries also provide the methods to order the contents of a vector as a heap.
Source: This algorithm is hardly original. The Sieve of Eratosthenes is a classical approach. This particular implementation was suggested by a data structures book I have by Augenstein and Tenenbaum, which is nearly as ancient. (The application language is PL/I, which gives a clue.) My implementation is rather different from theirs (better, I think), but omits some optimizations which they suggest.