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]
for n in range(2, 1000):
for x in range(2, n):
if n % x == 0:
break
else:
print n, ‘is a prime number’
btw when i tried to run it in idle 2.6.2 it said there was an error with the indentations… mine functions, is simple and quickly turns out the prime numbers
simply adjust the second number in the range (currently 1000) to any number you want to get the results for the given bracket