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

sieve-of-eratosthenes (python) (Python recipe) by Rahul Raj
ActiveState Code (http://code.activestate.com/recipes/577228/)

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

Python, 41 lines
Download
 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=[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()
Tags: algorithm, efficient, sieve

3 comments

AJ. Mayorga 13 years, 11 months ago  # | flag

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 13 years, 11 months ago  # | flag

Isn't this faster?

def sieve(n): sqrtn = int(n**0.5) sieve = [True] * (n+1) sieve[0] = False sieve[1] = 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 13 years, 11 months ago  # | flag

here we go again...

def sieve(n):
sqrtn = int(n**0.5)
sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = 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)
◄ Python recipes (4591) ►
◄ Rahul Raj's recipes (1) ►

Required Modules

  • (none specified)

Other Information and Tasks