title: Fastest way to list all primes below N
body: <p>This is the best algorithm I could come up.</p>
  
  <pre><code>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
  
  &gt;&gt;&gt; timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
  1.1499958793645562
  </code></pre>
  
  <p>Can it be made even faster?</p>
  
  <p>This code has a flaw: Since <code>numbers</code> is an unordered set, there is no guarantee that <code>numbers.pop()</code> will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers:</p>
  
  <pre><code>&gt;&gt;&gt; sum(get_primes(2000000))
  142913828922L
  #That's the correct sum of all numbers below 2 million
  &gt;&gt;&gt; 529 in get_primes(1000)
  False
  &gt;&gt;&gt; 529 in get_primes(530)
  True
  </code></pre>