Создание итерируемого объекта простого числа в Python

Question

Я пытаюсь выучить итераторы в Python, и на практике я пытаюсь построить итерируемый объект, который предоставляет простые числа до указанного предела.

Идея состоит в том, что класс можно использовать для создания объекта, который содержит список простых чисел до предела, заданного пользователем.

Лог c Я использую:

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
%

Классная проблема!