Skip to content

Instantly share code, notes, and snippets.

@azalea
Created January 8, 2012 08:59
Show Gist options
  • Save azalea/1577768 to your computer and use it in GitHub Desktop.
Save azalea/1577768 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
def sieveEratosthenes(limit):
'''Return all primes below the limit'''
numbers = range(3,limit,2)
primes = [2]
while True:
prime = numbers.pop(0)
primes.append(prime)
for n in range(prime**2, limit, 2*prime):
try:
numbers.remove(n)
except ValueError:
pass
if prime**2 > limit:
primes.extend(numbers)
break
return primes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment