Skip to content

Instantly share code, notes, and snippets.

@owainlewis owainlewis/sieve.py
Created Apr 4, 2012

Embed
What would you like to do?
Sieve of Erastothenes
from math import sqrt
# Sieve of Erastothenes
def sieve(n):
candidates = list(range(n))
# We only need to check up to the square root of n
upto = int(sqrt(n)) + 1
# Loop over the candidates, marking out each multiple as None.
for i in list(range(2, upto)):
if not candidates[i]:
continue
# mark out each multiple of i
for x in range(2 * i, n, i):
candidates[x] = None
# Filter out non-primes and return the list.
return list(filter(lambda x : x != None, candidates))[2:]
print(sieve(30))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.