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]


One Response to “Fast Prime Number Generator in Python”  

  1. 1 really simple

    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

Leave a Reply



 

Bad Behavior has blocked 14 access attempts in the last 7 days.