Генерация рекурсии в сите Эратосфена пропускает шаги

Question

Я столкнулся с проблемой с алгоритмом сита, который я написал здесь.Я пытался исправить это в общей сложности около 10 часов.Я искал здесь похожие вопросы, но я не могу найти никого, кто имел эту проблему.Я относительно новичок в Python, и после прочтения большого количества документации генератора мне удалось написать код, который работает.Тем не менее, я до сих пор не знаю, почему мои первые попытки не увенчались успехом.

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

Буду очень признателен за понимание этого и за любые предложения по улучшению того, что у меня сейчас есть.

Вот код ошибки:

def primes(n):
    "yields primes up to n. For use with large n"
    q = 0
    yield 2
    gen1 = (x for x in range(3,n,2))
    while q*q < n:
        q = next(gen1)
        gen1 = (x for x in gen1 if x%q != 0)
        yield q
    else:
        while 1:
            try:
                yield next(gen1)
            except:
                StopIteration
                break

Вот мой текущий код:

import math
global gen1
global gen
def gen1(x):
    for i in range(3,x,2):
        yield i
def gen(generator,n):
    "Input generator and current starting 'index' for the generator"
    # Recursively defines new generator for sieve of Eratosthenes
    for i in range(n+1):
        predicate = next(generator)
        yield predicate
    for i in generator:
        if i % predicate != 0:
            yield i
def primes(n):
    yield 2
    a = gen1(n)
    for i in range(math.ceil(math.sqrt(n))):
        a = gen(a,i)
    yield from a

Answer 1

Основная проблема связана с областью применения.В этой строке:

  gen1 = (x for x in gen1 if x%q != 0)

используемое значение q равно , а не значение q было привязано к моменту, когда выражение генератора было создано , а точнее (постоянно меняющееся!) значение q в то время, когда выражение генератора выполняет .Это работает так же, как и для ссылки на нелокальные переменные во вложенных функциях любого типа.

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

def primes(n):
    "yields primes up to n. For use with large n"

    def gen(gen1, q):
        for x in gen1:
            if x % q:
                yield x

    q = 0
    yield 2
    gen1 = iter(range(3, n, 2))
    while q*q < n:
        q = next(gen1)
        gen1 = gen(gen1, q)
        yield q
    yield from gen1

Теперь значения, используемые в теле gen(), являются именно теми, которые ему переданы, так что это очевидно, а не загадка;-)