ActiveState Code

Recipe 576596: Sieve of Eratosthenes

Returns primes < n.

Python 
1
2
3
4
5
6
7
def eratosthenes(n):
    N=range(n+1)
    z=[0]*(n/2)
    for i in range(2, int(n**.5)+1):
        if N[i]:
            N[i*i::i] = z[:(n/i)-i+1]
    return filter(None, N[2:])

Discussion

see :
- here and here
- Recipe 117119

Comments

  1. 1. At 3:15 a.m. on 28 dec 2008, Louis Riviere (the author) said:

    Here is an alternative that may be more readable, slower though.

    def eratosthenes(n):  
    N=range(n+1)  
    z=[0]*(n+1)  
    for i in range(2, int(n**.5)+1):  
        if N[i]:  
            N[i*i::i] = z[i*i::i]  
    return filter(None, N[2:])

Sign in to comment