I was looking at this article (The Genuine Sieve of Eratosthenes / PDF) about a common functional prime number generator that is mistakenly called the Sieve of Eratosthenes.

It is quite complicated, section 2 deals with the performance of the naive algorithm and 3 implements the sieve properly. I could not quite grok the Haskell but the following quote helped me know what was going on

Whereas the original algorithm crosses off all multiples of a prime at once, we perform these “crossings off” in a lazier way: crossing off just-in-time. For this purpose, we will store a table in which, for each prime p that we have discovered so far, there is an “iterator” holding the next multiple of p to cross off. Thus, instead of crossing off all the multiples of, say, 17, at once (impossible, since there are infinitely many for our limit-free algorithm), we will store the first one (at 17 × 17; i.e., 289) in our table of upcoming composite numbers. When we come to consider whether 289 is prime, we will check our composites table and discover that it is a known composite with 17 as a factor, remove 289 from the table, and insert 306 (i.e., 289+17). In essence, we are storing “iterators” in a table keyed by the current value of each iterator.

Here it is using a dictionary for each composite number with a list of increments it was reached by:

from itertools import count

def gen_primes():
yield 2
def update_composites(number,increment):
try:
composites[number] += [increment]
except:
composites[number] = [increment]

composites = {4:[2]}

c = count(3)
while 1:
#print composites
next = c.next()
smallest = min(composites.keys())
incs = composites[smallest]
del composites[smallest]
for inc in incs:
update_composites(smallest+inc,inc)
if next < smallest:
yield next
c.next()
update_composites(next**2,next)

g=gen_primes()

for i in range(100):
print g.next()


(On Github)

They mention a speedup moving to a heapqueue as the data structure (as we just take the lowest each lookup) so I implemented that too, here is the code

from itertools import count
from heapq import heappush,heappop

def gen_primes():
yield 2

def update_composites(number,increment):
heappush(composites,(number,increment))
composites = [(4,2)]

c = count(3)

while 1:
#print composites
smallest,increment = heappop(composites)
update_composites(smallest+increment,increment)
if composites[0][0] == smallest:
continue
next = c.next()
if next < smallest:
yield next
c.next()
update_composites(next**2,next)

g=gen_primes()

for i in range(100):
print g.next()


(On github)