Welcome, guest | Sign In | My Account | Store | Cart

sieve-of-eratosthenes algorithm with efficient scaling for big numbers.

Python, 41 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42``` ```#!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= 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() ``` AJ. Mayorga 12 years, 4 months ago

I think you demonstrate the "Math" of eratosthenes very well, in your code, but think from a pythonic point of view you could gen primes somewhat more efficent1y using a modified sieve of atkin (I dont know I'm a code guy who likes math, not a math guy who like code so I could be WAY OFF) for an example see http://code.activestate.com/recipes/577229/ Robert W. Hanks 12 years, 4 months ago

Isn't this faster?

def sieve(n): sqrtn = int(n**0.5) sieve = [True] * (n+1) sieve = False sieve = False

``````for i in range(2, sqrtn+1):
if sieve[i]:
m = n//i - i
sieve[i*i:n+1:i] = [False] * (m+1)

sieve = [i for i in range(n+1) if sieve[i]]

return len(sieve) # return len for speed test
``````

any sugestions to improve this code? Robert W. Hanks 12 years, 4 months ago

here we go again...

``````def sieve(n):
sqrtn = int(n**0.5)
sieve = [True] * (n+1)
sieve = False
sieve = False

for i in range(2, sqrtn+1):
if sieve[i]:
m = n//i - i
sieve[i*i:n+1:i] = [False] * (m+1)

sieve = [i for i in range(n+1) if sieve[i]]
return len(sieve)
`````` Created by Rahul Raj on Sat, 15 May 2010 (MIT)

### Required Modules

• (none specified)