A Lazy Sieve of Eratosthenes

Sunday 23 June 2013

The Sieve of Eratosthenes can be simulated elegantly using a heap.

The Sieve of Eratosthenes is a popular exercise for beginner programmers. It involves finding all the prime numbers up to N. But traditionally, N has to be a constant that you know before you start, as you have to allocate a large array so that composite numbers can be "crossed off".

I found a wonderful paper that examined how to implement the Sieve in Haskell, which is keen on lazily evaluating lists. "Lazy" means that each element is only calculated when it's needed, rather than up-front.

As usual, I'll implement it in Go, using package heap, which I've written about before.

The idea is that each prime can generate a list of its multiples - i.e. composite numbers (non-primes). If you've found all the primes <=sqrt(N), then you can find all the primes <=N by crossing off the multiples of the known primes. Once you've removed the composites, the numbers left must be prime.

Each generator contains the prime, and the multiple that it will generate next.

type generator struct {
    prime    int64
    multiple int64

We create a heap of these generators, sorted so that we pop the one with the lowest multiple, or smallest composite number.

type genHeap []generator
    h := make(genHeap, 0)
    heap.Push(&h, generator{2, 4})
We start with the generator for the first prime, 2, in the heap. Its next multiple is 4. Remember, we're sorting on the value of multiple.

We pop the next smallest composite number:

Finally, once a generator has been popped from the heap, we increment its multiple and push it back on, thus generating the next composite.
    for i := int64(3); i < int64(*n); {
        composite := heap.Pop(&h).(generator)
        if i < composite.multiple {
            //i is prime
            fmt.Print(i, " ")
            heap.Push(&h, generator{i, i * i})
        } else if i == composite.multiple {
            composite.multiple += composite.prime
        } else {
            composite.multiple += composite.prime
        heap.Push(&h, composite)

You can play with the code here, which also shows the code needed for package heap. The paper mentioned earlier has many ideas for optimization that could be used here.

This lazy method of generating primes removes the need to allocate a large array up front - or indeed at all!

Previous (Go's range clause)
Next (Random Graphs)