Returns primes < n.
Python, 7 lines
Download
Copy to clipboard1 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:])
|
see :
- here and here
- Recipe 117119
Here is an alternative that may be more readable, slower though.