Lazy List Generator Problem

[Gerald Britton]

For those interested in the Sieve of Eratosthenes, have a look at:

http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

The examples in the paper are in Haskell, but I have been
corresponding with the author who provided this Python version:

def sieve():
    innersieve = sieve()
    prevsquare = 1
    table  = {}
    i = 2
    while True:
        if (table.has_key(i)):
            prime = table[i]
            del(table[i])
            next = i+prime
            while next in table:
                 next = next + prime
            table[next] = prime
        else:
            yield i
            if i > prevsquare:
                j = innersieve.next()
                prevsquare = j * j
                table[prevsquare] = j
        i = i + 1

Only of 65056 bytes (less than 1/16 MB) of heap is used when
calculating the millionth prime.  It is also very fast but can be even
further optimized using a wheel as described in the paper.  FWIW I was
so intrigued I went off to learn Haskell just so I could follow the
paper properly.