在 Python 中构建质数可迭代对象

Question

我正在尝试学习 Python 中的迭代器，作为练习，我正在尝试构建一个可迭代对象，它提供不超过指定限制的素数。

想法是 class 可用于创建一个对象，该对象包含一个不超过用户给定限制的素数列表。

我使用的逻辑：

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

以下是我正在处理的代码：

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

这是一场灾难！您正在为 return 素数创建一个迭代器，但在内部您正在使用相同的迭代器生成素数除数以查看数字是否为素数。实际上，迭代器在尝试得出 return 值时耗尽它。或类似的东西。相反，在内部，我们需要创建此迭代器的一个新实例（具有更小的限制）来生成素因数。（即递归。）类似于：

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
%

很酷的问题！

在 Python 中构建质数可迭代对象

Building a Prime Number Iterable Object in Python

python

recursion

iterator

iterable