How can I speed up a script that iterates over a large range (600 billion)?

[Ian Kelly]

On Wed, Jun 22, 2011 at 6:01 AM, Anny Mous <b1540457 at 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