CODEWITHSUNDEEP
pythonpython-3.xiterator
Sairaj K
Sairaj K

Reputation: 142

How does this __iter__ and __next__ algorithem work? How does it print all those prime numbers?

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)

Output:

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

Upvotes: 0

Views: 95

Answers (2)

chepner
chepner

Reputation: 531808

For large (or possibly infinite) bounds, a more (memory-)efficient implemention would use generators:

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

When Sieve is first instantiated, the candidates attribute is a sequence of integers starting with 2.

__next__ has one precondition: the first element of the candidates attribute must be a prime number. This is satisfied by the first call because 2 is a prime number.

__next__ then

  1. Removes the first element from candidates and calls it prime
  2. Replaces candidates with a new iterable that consists only of those former candidates that are not divisible by prime.

These two actions fulfill the precondition for the next call to __next__, as the ith call to __next__ removes all numbers divisible by the ith prime number. Thus each remaining candidate is not divisible by any previously seen prime number.

Upvotes: 0

norok2
norok2

Reputation: 26896

The source of the actual information is here:

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

which contain the sieve of Eratosthenes.

The __iter__ and __next__ method, are special Python methods to have a class behave like an iterator.

Upvotes: 2

Related Questions