0
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]
Tomerikoo
  • 18,379
  • 16
  • 47
  • 61
Sairaj K
  • 138
  • 1
  • 10
  • Each time it returns another prime, it removes all the multiples of that prime from its candidates list. That way any non-primes are removed before they are reached. – khelwood May 28 '20 at 13:20

2 Answers2

2

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.

norok2
  • 25,683
  • 4
  • 73
  • 99
  • But how does 2 get added in the list when 2 % 2 is zero?? – Sairaj K May 28 '20 at 13:53
  • 2
    `2` is on the original list. It is retrieved *before* all multiples of 2 are removed. On the next call, 3 is retrieved before all multiples of 3 are removed, etc. – chepner May 28 '20 at 13:54
0

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.

chepner
  • 497,756
  • 71
  • 530
  • 681
  • This does not work when specifying `bound`, since `range()` is not an Iterator. You should replace it with `iter(range())`. – norok2 May 28 '20 at 14:02
  • Also the infinite bound is purely theoretical, since for `bound` as low as `8000` (in a standard Python installation) you would hit the `RecursionError: maximum recursion depth exceeded in comparison` error, due to the fact that each generator is spawning a new generator. This happens regardless of whether a `bound` is specified or not. – norok2 May 28 '20 at 14:06
  • 1
    I was trying to avoid using `filter` and a user-defined function, but I guess I can't. – chepner May 28 '20 at 16:37