python - 在循环内保留过滤器输出

Question

我正在尝试以下操作来生成素数直到给定的限制。我想到了使用埃拉托色尼筛。当我使用列表时，我得到了正确的输出，但是当我没有将它作为列表时，输出是错误的并返回所有数字。有没有一种方法可以通过递归来做到这一点，并且由于python中存在递归限制，是否还有其他方法可以使用以下结构。我通读了 Rosetta 代码，以检查使用集合的实现以及使用字典将数字设置为非素数的列表。

def prime_till(number):
    seq = range(2, number)
    while True:
        try:
            first = seq.__next__()
        except AttributeError:
            first = seq.__iter__().__next__()
        except StopIteration:
            return None
        yield first
        seq = list(filter(lambda x: x % first != 0, seq))

print(list(prime_till(20)))

输出:

[2, 3, 5, 7, 11, 13, 17, 19]

没有列表:

def prime_till(number):
    seq = range(2, number)
    while True:
        try:
            first = seq.__next__()
        except AttributeError:
            first = seq.__iter__().__next__()
        except StopIteration:
            return None
        yield first
        seq = filter(lambda x: x % first != 0, seq)

print(list(prime_till(20)))

输出:

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Answer 1

我不是 Python 专家，但我已经对您的代码进行了一些调试。看起来，lambda 表达式是在读取序列时计算的。也就是说，在实际表达式 x % first 中，first 每次都被替换为 first 的当前值，而不是您创建过滤器时的那个。

这里有一些奇怪的代码来证明这一点:

def prime_till(number):
    seq = iter(range(2, number))
    while True:
        try:
            first = next(seq)
            print(first)
        except StopIteration:
            return None

        if first == 2:
            seq = filter(lambda x: x % 2 != 0, seq)
        elif first == 3:
            seq = filter(lambda x: x % 3 != 0, seq)
        elif first == 5:
            seq = filter(lambda x: x % 5 != 0, seq)
        else:
            seq = filter(lambda x: x % first != 0, seq)

        if first == 5:
            print(list(seq))

prime_till(20)

结果:

2
3
5
[7, 11, 13, 17, 19]

这是关于同一主题的另一个答案:Deferred evaluation in python

现在，至于如何解决这个问题，我真的不知道，但我正在调查。

添加: 我已经使用@schlamar 在我链接的其他问题中描述的想法构建了一些工作代码。

from functools import partial

def modnotnull(denom, value):
    return value%denom != 0

def prime_till(number):
    seq = iter(range(2, number))
    while True:
        try:
            first = next(seq)
        except StopIteration:
            return None

        yield first
        seq = filter(partial(modnotnull,first), seq)
        #Or a one-liner:
        #seq = filter(partial(lambda denom,value: value%denom != 0,first), seq)

print(list(prime_till(20)))

输出:

[2, 3, 5, 7, 11, 13, 17, 19]

解释:

首先，我定义了一个 modnotnull 函数，它对给定的值和分母执行所需的检查。然后，每次绘制 first 值时，我都会使用 functools 中的 partial 函数从中创建一个新函数。基本上，我按照我在第一个示例中展示的方式动态创建不同的 lambda。 partial(modnotnull,2) 变为 lambda value: value % 2 != 0 等等。实际上，这会强制 python 在创建过滤器时评估我的参数之一。