#!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()
