Python Prime Number Generator (Sieve Algorithm demystified)

Posted: October 19, 2008 in Programming, Python, Software
Tags: , , , , ,

#The prime number generator is using Sieve algorithm for fast prime number computaion. The following are the steps of the algorithm:
#
#Algorithm:
#==========
#
#   Step 1. Consider a contiguous list of numbers from two to some maximum. (This is the list of squares on the left side of the picture.)
#
#   Step 2. Strike off all multiples of 2 greater than 2 from the list.
#
#   Step 3. The next highest, uncrossed off number in the list is a prime number.
#
#   Step 4. Strike off all multiples of this number from the list. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
#
#   Step 5. Repeat steps 3 and 4 until you reach a number greater than or equal to the square root of the highest number in the list; all the numbers remaining in the list are prime.
#
#Source: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

import math

def primeNumGenerator(input):

#Here if the input is less than 2, then return an empty list since the smallest prime number is 2
if input < 2: return []

#If input is 2, then return 2
if input == 2: return [2]

# Steps 1&2 of the algorithm – We are here considering a contiguous list of number from 2 to given imput. Setting step of 2 in the range function strikes off all multiples of 2 greater than 2 from the list
s = range(3, input, 2)
mroot = math.sqrt(input)
listofinput = len(s)
i = 0
# Step 3 of the algorithm. We start with number 3 in the list as we have already considered scenarios till number 2 in the list above
m = 3

#As per prime number generator theorm, the numbers in the list are only checked till the square root of the number for which the prime number series is to be generated
while m <= mroot:
if s[i]:
#Step 4 of the algorithm. To strike off all multiples of this number from the list, we need to first calculate the index of the multiple in the list.
#The formula for doing so is (m*m-1). But since we are considering only odd number series, the formula gets modified to: (m*m-1)/2.
#Now since our odd number series does not have 1 (or has a member missing), the formula further gets modified to: ((m*m-1)/2)-1 = (m * m – 3)/2
#Also floor division is used here (//) since only the integer part is needed for index
j = (m * m – 3)//2
#  Step 4 of the algorithm continued. Striking off multiple of this number
s[j] = 0
#   Continuing to striking all other multiples of this number from the list
while j < listofinput:
s[j] = 0
j += m
#  Increasing the index to process with the next number in the list
i = i + 1
#        Now the nth element in a odd number series is (2n+1) where n is the index. Since our list starts with 3, the formula gets gets modied to:
#        2(m+1)+1 = 2m+3 which gives us the next number in the series
m = 2 * i + 3

#   Using list comprehension to build the prime number series. First we are adding 2 to the series since we didn’t consider 2 in our series are 2 is prime. Now all the indexes not marked as 0 are the prime numbers
return [2]+[prime for prime in s if prime]

if __name__ == ‘__main__’:
num = 20
primeNumberList = primeNumGenerator(num)
print “List of prime numbers from 2 to < %d:” % num
print primeNumberList

Comments
  1. David says:

    Thanks! This was very helpful for me! One thing, I’ve noticed a speedup in the algorithm by switching from floor division in the index calculation to standard division. Since you’re squaring an odd number the result of that squaring will always be odd, and 3 subtracted from any odd number will always be even, so it will always divide evenly by two and result in a clean integer value.

  2. Martin says:

    Thank you, though it crashes when the input is the square of a prime, e.g. 49. It returns an IndexError as the last index, in this case 29 = (7*7-3)/2, is larger than the number of elements in the list s. In seems to be fixed by simply changing the definition of the list s so that the range maximum is input+1 rather than input.

    • Martin says:

      Ah, this also changes it to list every prime less than or equal to input, rather than only less than. This maybe isn’t a problem if one is aware of it. And one could easily chop off the last element.

  3. Gary Croft says:

    Speaking of demystification: This algorhythmic sieve and/or array may provide clues to accelerating prime number crunching calculations. As I am a bonehead arithmatician, I leave that to “real” mathematicians.

    http://www.primesdemystified.com/

    Cheerio,
    Gary Croft
    gwc@hemiboso.com

  4. […] Python Prime Number Generator (Sieve Algorithm demystified) October 2008 5 comments 5 […]

  5. Chris Kavanagh says:

    Thank you!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s