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

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

338 голосов
/ 15 января 2010

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

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

Ответы [ 31 ]

0 голосов
/ 15 апреля 2013

Я могу опоздать на вечеринку, но мне придется добавить свой код для этого. Он использует примерно n / 2 в пространстве, потому что нам не нужно хранить четные числа, и я также использую модуль python bitarray, что значительно сокращает потребление памяти и позволяет вычислять все простые числа до 1 000 000 000 

from bitarray import bitarray
def primes_to(n):
    size = n//2
    sieve = bitarray(size)
    sieve.setall(1)
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            sieve[(i+i*val)::val] = 0
    return [2] + [2*i+1 for i, v in enumerate(sieve) if v and i > 0]

python -m timeit -n10 -s "import euler" "euler.primes_to(1000000000)"
10 loops, best of 3: 46.5 sec per loop

Это было выполнено на 64-битной Mac OSX с частотой 2,4 ГГц 10.8.3

Страница:
...