On Wed, Jun 22, 2011 at 6:01 AM, Anny Mous <b1540...@tyldd.com> wrote: > def sieve(): > """Yield prime integers efficiently. > > This uses the Sieve of Eratosthenes, modified to generate the primes > lazily rather than the traditional version which operates on a fixed > size array of integers. > """ > # This implementation based on a version by Melissa E. O'Neill, > # as reported by Gerald Britton: > # http://mail.python.org/pipermail/python-list/2009-January/1188529.html > innersieve = sieve() > prevsq = 1 > table = {} > i = 2 > while True: > if i in table: > prime = table[i] > del table[i] > nxt = i + prime > while nxt in table: > nxt += prime > table[nxt] = prime > else: > yield i > if i > prevsq: > j = next(innersieve) > prevsq = j**2 > table[prevsq] = j > i += 1
This appears to have a small bug in it, but perhaps it doesn't matter. At the "yield i" statement, it is possible that i > prevsq. It could be that i == next(innersieve)**2, in which case i is yielded as prime despite being composite. This would then cause additional errors further along. The only way this could happen would be if there were two consecutive primes such that all the numbers between their squares are composite, thereby failing to add the next prime to the table until after its square has been reached. This seems a rather unlikely scenario, but I can't say for certain that it never happens. The Haskell version does not contain this flaw, as far as I can tell. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
