#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

### Like this:

Like Loading...