This is the best algorithm I could come up.
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?
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