Как работает этот алгоритм __iter__ и __next__? Как он печатает все эти простые числа?

Question

class PrimesBelow():
    def __init__(self,bound):
        self.candidate_numbers = list(range(2,bound))

    def __iter__(self):
        return self

    def __next__(self):
        if len(self.candidate_numbers) == 0:
            raise StopIteration
        next_prime = self.candidate_numbers[0]
        self.candidate_numbers = [x for x in self.candidate_numbers if x % next_prime != 0]
        return next_prime
primes_to_hundread = [prime for prime in PrimesBelow(100)]
print(primes_to_hundread)

Вывод:

[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]

Answer 1

Источник актуальной информации находится здесь:

[x for x in self.candidate_numbers if x % next_prime != 0]

которые содержат сито Эратосфена .

Метод __iter__ и __next__, это специальные методы Python, позволяющие классу вести себя как итератор .

Answer 2

Для больших (или, возможно, бесконечных) границ более эффективная реализация (с точки зрения памяти) будет использовать генераторы:

from itertools import count
from math import gcd


class Sieve:
    def __init__(self, bound=None):
        self.candidates = count(2) if bound is None else iter(range(2, bound))

    def __iter__(self):
        return self

    def __next__(self):
        prime = next(self.candidates)
        self.candidates = filter(lambda x, d=prime: x % d != 0, self.candidates)
        return prime

Когда Sieve создается впервые, атрибут candidates представляет собой последовательность целые числа, начинающиеся с 2.

__next__ имеет одно предварительное условие: первый элемент атрибута candidates должен быть простым числом. Это удовлетворяется первым вызовом, потому что 2 - простое число.

__next__ затем

1. Удаляет первый элемент из candidates и вызывает его prime
2. Заменяет candidates на новую итерацию, состоящую только из тех бывших кандидатов, которые не делятся на prime.

Эти два действия выполняют предварительное условие для следующего вызова __next__, так как i -й вызов __next__ удаляет все числа, делящиеся на i -ое простое число. Таким образом, каждый оставшийся кандидат не делится на какое-либо ранее увиденное простое число.