Как реализовать эффективный бесконечный генератор простых чисел в Python? - PullRequest
Новая
       65

Как реализовать эффективный бесконечный генератор простых чисел в Python?

58 голосов
/ 06 февраля 2010

Это не домашняя работа, мне просто любопытно.

БЕСКОНЕЧНОЕ ключевое слово здесь.

Я хочу использовать его как for p in primes(). Я считаю, что это встроенная функция в Haskell.

Таким образом, ответ не может быть таким наивным, как "Просто сделай сито".

Прежде всего, вы не знаете, сколько последовательных простых чисел будет использовано. Ну, предположим, вы могли бы придумать 100 из них одновременно. Будете ли вы использовать тот же метод сита, а также формулу частоты простых чисел?

Я предпочитаю не параллельный подход.

Спасибо, что читаете (и пишете;))!

Ответы [ 13 ]

1 голос
/ 06 февраля 2010

Несколько раз назад я написал статью о генераторе бесконечных простых чисел:

http://stacktrace.it/2008/01/progetto-eulero-problema-3/

Это на итальянском, но вы можете сделать досадный перевод с помощью Google: http://tinyurl.com/yzpyeom

1 голос
/ 06 февраля 2010

Вот генератор, который немного правдивее того, как это делается в Haskell: фильтрация по композициям известных простых чисел, а затем добавление оставшихся простых чисел в список. 

def gen_primes():
    primes = []
    i = 2
    while True:
        prime = True
        for p in primes:
            if not (i % p):
                prime = False
                break
        if prime:
            yield i
            primes.append(i)
        i += 1
0 голосов
/ 17 мая 2018

Я знаю, что пост старый, но я сам наткнулся на этот вопрос ... Следующий код основан на очень простой идее: растущее сито Эратосфена.Это решение действительно медленнее, чем лучшие здесь, но его легко понять и оно разработано так, чтобы его можно было читать ...

Я использовал целые числа для хранения результатов сита.В двоичном формате целое число представляет собой список 0 s и 1 s, 0 в позиции i, если i не является простым числом, 1, если это может быть простым числом.Необходимая бесконечность является результатом того, что целые числа Python 3 не ограничены. 

def primes():
    container, size = 1 << 2, 3 # we start with 0b100 (from right to left: 0 and 1 are not primes, 2 is
    last_prime = 1
    while True:
        prime = next((j for j in range(last_prime+1, size) if container & 1 << j), None) # find the next prime
        while not prime:
            container, size = expand(container, size, 2**16) # add 65536 cells and sieve the container
            prime = next((j for j in range(last_prime+1, size) if container & 1 << j), None)
        yield prime
    last_prime = prime

Как расширить контейнер?Просто добавьте связку 1 слева от контейнера (в двоичном формате) и просейте их.Это идентично стандартному сита с небольшой разницей.В стандартном сите, если мы находим простое число i, мы начинаем пересекать ячейки в i*i с шагом i.

Здесь это может быть сделано для первой частиконтейнера.Нам просто нужно начать с начала новой части контейнера, если она дальше, чем i*i. 

def expand(container, size, n):
    new_size = size + n
    container += (1 << (new_size + 1) - 1) - (1 << size) # add n 1's
    for i in range(2, new_size):
        if container & (1 << i): # i is a prime
            t = sum(1 << j for j in range(max(i, size // i)*i, new_size, i)) # set 1 for all mutiple
            container &= ~t # cross the cells

    return container, new_size

Проверка на миллион простых чисел: 

import itertools
assert 78498 == len(list(itertools.takewhile(lambda p: p<1000000, primes())))
Страница:
...