*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.Init(&h) 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:

- If it is equal to our counter, then our counter is clearly not prime.
- If our counter is less than the composite, then our counter must be prime, since we're popping the composites in order. When we find a prime, we create a new generator that will produce all of its multiples, and we increase our counter so that we only have one generator for each prime.
- Otherwise, our counter is more than the composite, so we need to pop more composites off the heap to catch up.

`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}) i++ } else if i == composite.multiple { composite.multiple += composite.prime i++ } 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!