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

[Гость]

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

Код: Выделить всё

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

Источник: https://stackoverflow.com/questions/206 ... es-below-n