Finding a Prime Sieve Inconsistency in Python -

i'm attempting learn python , thought trying develop own prime sieve interesting problem afternoon. when required far, import version of sieve of eratosthenes found online -- it's used benchmark.

after trying several different optimizations, thought had written pretty decent sieve:

def sieve3(n): top = n+1 sieved = dict.fromkeys(xrange(3,top,2), true) si in sieved:     if si * si > top:         break     if sieved[si]:         j in xrange((si*2) + si, top, si*2):       [****]             sieved[j] = false return [2] + [pr pr in sieved if sieved[pr]] 

using first 1,000,000 integers range, code generate correct number of primes , 3-5x slower benchmark. give , pat myself on when tried on larger range, no longer worked!

n = 1,000 -- benchmark = 168 in 0.00010 seconds n = 1,000 -- sieve3 = 168 in 0.00022 seconds  n = 4,194,304 -- benchmark = 295,947 in 0.288 seconds n = 4,194,304 -- sieve3 = 295,947 in 1.443 seconds  n = 4,194,305 -- benchmark = 295,947 in 3.154 seconds n = 4,194,305 -- sieve3 = 2,097,153 in 0.8465 seconds 

i think problem comes line [****], can't figure out why it's broken. it's supposed mark each odd multiple of 'j' false , works of time, above 4,194,304 sieve broken. (to fair, breaks on random other numbers too, 10,000 instance).

i made change , slowed code down, work values. version includes numbers (not odds) otherwise identical.

def sieve2(n): top = n+1 sieved = dict.fromkeys(xrange(2,top), true) si in sieved:     if si * si > top:         break     if sieved[si]:         j in xrange((si*2), top, si):             sieved[j] = false return [pr pr in sieved if sieved[pr]] 

can me figure out why original function (sieve3) doesn't work consistently?

edit: forgot mention, when sieve3 'breaks', sieve3(n) returns n/2.

the sieve requires loop on candidate primes ordered. code in question enumerating keys of dictionary, not guaranteed ordered. instead, go ahead , use xrange used initialize dictionary main sieve loop return result loop follows:

def sieve3(n):     top = n+1     sieved = dict.fromkeys(xrange(3,top,2), true)     si in xrange(3,top,2):         if si * si > top:             break         if sieved[si]:             j in xrange(3*si, top, si*2):                      sieved[j] = false     return [2] + [pr pr in xrange(3,top,2) if sieved[pr]]