Mar 24, 2012



In mathematics, the sieve of Eratosthenes , is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

You can reed the full description on wikipedia here

This is my implememntation

 def compute(n=100):  
     seq = range(2,n)  
     p = 2  
     while p < n and len(range(2*p,n,p)):  
         jumpy = range(2*p,n,p)  
         for j in jumpy:  
             if seq.count(j) > 0:  
                 seq.remove(j)  
         p = seq[1+seq.index(p)]  
     print "Prime nums from 2 to " , n , " : ", seq  
     return seq  
 def test():  
     expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]  
     out_list = compute()  
     for o in out_list:  
         assert( expected.count(o) > 0 )