Fastest way to list all primes below N in python
- by jbochi
This is the best algorithm I could come up with after struggling with a couple of Project Euler's questions.
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1)
1.1499958793645562
Can it be made even faster?
EDIT: This code has a flaw: Since numbers is an unordered set, there is no guarantee that numbers.pop() will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers:
>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
EDIT: The rank so far (pure python, no external sources, all primes below 1 million):
Sundaram's Sieve implementation by myself: 327ms
Daniel's Sieve: 435ms
Alex's recipe from Cookbok: 710ms
EDIT: ~unutbu is leading the race.
