Самый быстрый способ перечислить все простые числа ниже N

Это лучший алгоритм, который я мог бы придумать.

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

можно ли сделать еще быстрее?

этот код имеет недостаток: с numbers неупорядоченный набор, нет никакой гарантии, что numbers.pop() удалит самый низкий номер из набора. Тем не менее, он работает (по крайней мере для меня) для некоторых входных чисел:

>>> 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