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. -- http://mail.python.org/mailman/listinfo/python-list