Eratosthenes 筛法中的生成器递归跳过步骤

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 的（不断变化的！）值。这与在任何类型的嵌套函数中引用非局部变量的方式相同。

要在创建时捕获绑定，显而易见且简单的方法是改为编写一个函数，并传递您希望它使用的值。例如，这个重写在这方面和其他几个方面更像 Python：

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() 正文中使用的值正是传递给它的值，所以它是显而易见的而不是神秘的;-)

Eratosthenes 筛法中的生成器递归跳过步骤

Generator Recursion in Sieve of Eratosthenes Skips Steps

python

recursion

generator

generator-expression

sieve-of-eratosthenes