用Python构建一个质数迭代对象

Question

我正在尝试学习Python中的迭代器，作为练习，我正在尝试建立一个可迭代的对象，它提供的素数最多可达到指定的极限。

我们的想法是，这个类可以用来创建一个对象，这个对象包含一个由用户给定的最大极限的素数列表。

我使用的逻辑是

1. 质数从2开始依次生成
2. 1被加到迄今为止序列中最大的质数上，并检查它们是否被迄今为止质数列表中的任何一个数字所除。
3. 如果这些数字被质数列表中的任何一个数字所除，则丢弃这些数字，并将1加到当前的数字上，得到下一个要尝试的数字。
4. 如果它们不能被列表中的任何一个质数整除，它们将被添加到列表中作为下一个质数。

以下是我正在研究的代码。

class PrimeList:
    def __init__(self,limit):
        self.val = 2
        self.limit = limit
    def __iter__(self):
        return self
    def __next__(self):
        if self.val >= (self.limit**0.5+1):
            raise StopIteration
        else:
            return_val = self.val
            while return_val < (self.limit**0.5+1):
                if is_prime(self, return_val+1): # Having problems in this step. Goes into an infinite loop
                    return return_val + 1
                else:
                    return_val +=1
            else:
                return return_val

def is_prime(list_of_primes,x):
    while True:
        try:
            y = next(list_of_primes)
            if x % y == 0:
                return False
        except StopIteration:
            return True

test = PrimeList(100)
print(list(test))

我得到的错误是 RecursionError: maximum recursion depth exceeded while calling a Python object

我想我不知道如何递归地引用可迭代对象。

希望得到任何帮助。

Answer 1

这真是一场灾难! 你创建了一个迭代器来返回质数，但在内部，你使用同一个迭代器来生成质数除数，以确定这个数字是否是质数。 实际上，当迭代器试图得出一个返回值时，它已经耗尽了迭代器。 或者类似的东西。 相反，在内部，我们需要创建一个新的迭代器实例（有一个较小的限制）来生成质数除数。 (也就是递归。)类似这样。

class PrimeList:
    def __init__(self, limit):
        self.limit = limit
        self.value = 2

    def __iter__(self):
        return self

    def is_prime(self, x):
        while True:
            try:
                y = next(self)

                if x % y == 0:
                    return False

            except StopIteration:
                return True

    def __next__(self):

        while self.value < self.limit:
            divisors = PrimeList(int(self.value ** 0.5) + 1)  # recursion

            found = divisors.is_prime(self.value)

            self.value += 1

            if found:
                return self.value - 1

        raise StopIteration()

test = PrimeList(100)
print(*test, sep=", ")

这样做可以，但速度会比较慢。

% python3 test.py
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
%

酷的问题！