Python in Detail: Prime Iterator Example

• In an earlier lesson, we created our own iterable data types. Their .__iter__ methods returned iterators, which kept track of the iteration progress while we looped over the data.

• This lesson explores a powerful fact about iterators: they can represent infinite amounts of data, or data streams that never end. For example, the data might be streamed over a network, or generated one element at a time. In this lesson, we'll build an infinite iterable that gives us all prime numbers.

• First, we need a way to find individual prime numbers. A number is prime if it's only divisible by itself and 1.

• We'll use the modulo operator, %, to test for divisibility. x % y gives the modulo or "remainder" of dividing x by y. For example, x % 2 tells us whether x is even or odd. x % 2 == 0 for even numbers and x % 2 == 1 for odd numbers.

• >

  99 % 2

  Result:

  1

• >

  100 % 2

  Result:

  0

• In the next example, we apply n % 4 to many numbers. The result is always between 0 and 3. Note that the modulos are cyclic: the count from 0 to 3, then start over again. Whenever the number is divisible by 4 (like 0, 4, 8, etc.), the modulo is 0.

• >

  numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  [n % 4 for n in numbers]

  Result:

  Run Code

• >

  14 % 4

  Result:

  2

• If n is prime, then n % i !== 0 for all integers i that are less than n.

• (The code shown below has a slightly more complex loop condition than that. It's still correct, but it improves performance.)

• >

  def is_prime(n):
    for i in range(2, n // 2 + 1):
      if n % i == 0:
        return False
    return True
• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  is_prime(2)

  Result:

  Run Code
• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  is_prime(100)

  Result:

  False
• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  is_prime(13)

  Result:

  True

• The Primes iterable is very simple: its .__iter__ method returns PrimesIterator, where the real work happens.

• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  class Primes:
    def __iter__(self):
      return PrimesIterator()

• PrimesIterator tracks which prime we're currently on. Its .__next__ method calls .increment_to_next_prime, which uses the is_prime function shown above to calculate the next prime number.

• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  class PrimesIterator:
    def __init__(self):
      self.current_prime = 2
  
    def __next__(self):
      current_prime = self.current_prime
      self.increment_to_next_prime()
      return current_prime
  
    def increment_to_next_prime(self):
      while True:
        self.current_prime += 1
        if is_prime(self.current_prime):
          return

• Now we have a working prime iterator! Below, we generate the first five primes: 2, 3, etc.

• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  my_iter = iter(Primes())
  (next(my_iter), next(my_iter), next(my_iter), next(my_iter), next(my_iter))

  Result:

  (2, 3, 5, 7, 11)

• Note that we only keep one number in memory: .current_prime. Each time we call .__next__, we start at that number, and count up until we find the next prime.

• There are infinitely many prime numbers, so our iterator is infinitely long. But we can consume only a few values from it, and that works perfectly well even on our finite computers.

• However, there's a danger here. If we use the iterator in a way that tries to bring all of its items into memory at once, that won't work. Calling list(Primes()) would load primes in an infinite loop, eventually running out of memory. We won't show that here because the infinite loop would lock your browser up. But we can dig deeper into the prime list to see that it really does work.

• Note: this code example reuses elements (variables, etc.) defined in earlier examples.

  >

  my_iter = iter(Primes())
  for _ in range(200):
    next(my_iter)
  next(my_iter)

  Result:

  Run Code

• Generating primes shows us how powerful iterators are. First, they can iterate over data even if we don't have all of the data yet (for example, if it's streaming over a network.) In that case, next(the_iterator) will have to wait ("block") until more data shows up.

• Second, as we saw with PrimesIterator, iterators can be infinite in length. Every computer is finite, so we can never load the full contents of an infinite iterator into memory. But iterators iterate over data only as it's needed, so they can represent infinite sequences of data without ever having to store it all in memory at the same time.

• In this lesson, our PrimesIterator class was quite long for such a simple task. That's good, because it lets us see the details of how an infinite iterator works. But there's also a much shorter way to write an infinite prime number iterator. In a future lesson on generators, we'll see that shorter version!