Ленивое сито эратосфена в питоне - PullRequest
Новая
       23

Ленивое сито эратосфена в питоне

6 голосов
/ 16 июля 2011

Я пытаюсь написать ленивую версию Sieve of Eratosthenes в Python 3.2. Вот код: 

import itertools
def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        yield prime

Однако, когда я перебираю простые числа (), я получаю только последовательные числа. Например., 

print(list(itertools.islice(primes(),0,10)))

печатает список 

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

К моему удивлению, следующая крошечная модификация простых чисел () заставляет его работать: 

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        next(itertools.tee(candidates)[1]) ########### NEW LINE
        yield prime

Полагаю, мне что-то не хватает в области параметров генератора 

candidates = (i for i in candidates if i % prime)

но я не вижу, как исправить код, не добавив эту случайно выглядящую новую строку. Кто-нибудь знает, что я делаю не так? Спасибо.

Ответы [ 3 ]

6 голосов
/ 16 июля 2011

исправление действительно заменить: 

candidates = (i for i in candidates if i % prime)

на: 

candidates = (lambda prime: (i for i in candidates if i % prime))(prime)
1 голос
/ 21 апреля 2012

Вот реализация Python оригинального первичного сита, основанного на коде haskell в статье: Подлинное сито эратосфена Мелиссы Э. О'Нил

Он не использует рекурсию или пробное деление, а скорее требует памяти. 

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: yield p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p,n,o,p))
    yield p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p,n,o,p))
            yield p
            continue
        while t[0][0] <= p:
            _,b,c,d = t[0]
            heapreplace(t, (b*d,b+w[c],(c+1)%l,d))

Следующее: 

import itertools
print list(itertools.islice(sieve(),0,10))

печать: 

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
1 голос
/ 16 июля 2011

Если вас беспокоит область действия переменных, создайте объекты / функции, чтобы сохранить эти переменные для вас: 

def filter_multiples(n, xs):
    for i in xs:
        if i % n
            yield i

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = filter_multiples(prime, candidates)
        yield prime

(у меня сейчас нет доступа к интерпретатору Pythonтак что я не знаю, работает ли это в конце концов или нет ...)

Кстати, алгоритм, который вы используете, на самом деле не является ситом Эрастотена.Загляните в эту классную статью, если у вас есть время: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

...