Fast Prime Number Generator in Python
I had this post saved as a draft for quite awhile. Python’s reliance on indentions made finding a code formatting plugin mandatory. This isn’t the fastest Python prime number generator, but it’s pretty good. I saw one somewhere else that was twice as fast, but it was a bit obtuse. This is a slight variation on the Sieve of Eratosthenes.
#------------------------------------------------------–
# optimized sieve - pretty good and still understandable
# generates primes up to 'limit'
#------------------------------------------------------–
def fast_primes( limit ):
if limit < 2:
return []
elif limit == 2:
return [2]
# fill the array with odds
map = range(3,limit+1,2)
stopat = limit ** 0.5
cur = mstart = 3
# only go up to the sqrt of the limit
while cur <= stopat:
multy = limit / cur
while( mstart <= multy ):
idx = ( cur*mstart-3 )/2
map[idx] = 0
mstart += 2
# get rid of this multiplier
mstart = cur + 2
# move up to the next digit
cur += 2
return [2] + [x for x in map if x]



No Responses to “Fast Prime Number Generator in Python”
Please Wait
Leave a Reply