The Sieve of Eratosthenes is an elegant algorithm for finding all the prime numbers up to some limit n. The basic idea is to first create a list of numbers from 2 to n. The first number is removed from the list, and announced as prime, and all multiples of this number is removed up to n are removed from the list. This process continues until the list is empty.

For example, if you wanted to find all the prime numbers up to 10, the list would contain 2, 3, 4, 5, 6, 7, 8, 9, 10. The 2 is removed and announced to be prime and 4, 6, 8, and 10 are removed since they are multiples of 2. That leaves 3, 5, 7, 9., repeat the process until the list is empty.

Write a program that prompts a user for n and then uses the sieve algorithm to find all the prime numbers less than or equal to n.

Check the explanation

Explanation:

#! usr/bin/python

#FileName: sieve_once_again. py

#Python Version: 2.6.2

#Author: Rahul Raj

#Sat May 15 11:41:21 2010 IST

fi=0 #flag index for scaling with big numbers ...

n=input ('Prime Number (>2) Upto:')

s=range (3, n, 2)

def next_non_zero ():

"To find the first non zero element of the list s"

global fi, s

while True:

if s[fi]:return s[fi]

fi+=1

def sieve ():

primelist=[2]

limit = (s[-1]-3) / 2

largest=s[-1]

while True:

m=next_non_zero ()

fi=s. index (m)

if m**2>largest:

primelist+=[prime for prime in s if prime] #appending rest of the non zero numbers

break

ind = (m * (m-1) / 2) + s. index (m)

primelist. append (m)

while ind<=limit:

s[ind]=0

ind+=m

s[s. index (m) ]=0

#print primelist

print 'Number of Primes upto %d: %d'% (n, len (primelist))

if __name__=='__main__':

sieve ()