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

Returns primes < n.

Python, 7 lines
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:])

1 comment

Louis RIVIERE (author) 12 years, 11 months ago  # | flag

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:])
Created by Louis RIVIERE on Fri, 26 Dec 2008 (MIT)
Python recipes (4591)
Louis RIVIERE's recipes (13)

Required Modules

  • (none specified)

Other Information and Tasks