Learning Scientific Programming with Python (2nd edition)

P2.5.8: The Sieve of Eratosthenes

Question P2.5.8

The algorithm known as the Sieve of Eratosthenes finds the prime numbers in a list $2, 3, \cdots, n$. It may be summarized as follows, starting at $p=2$, the first prime number:

  1. Mark all the multiples of $p$ in the list as non-prime (that is, the numbers $mp$ where $m=2,3,4,\cdots$: these numbers are composite.
  2. Find the first unmarked number greater than $p$ in the list. If there is no such number, stop.
  3. Let $p$ equal this new number and return to Step 1.

When the algorithm stops, the unmarked numbers are the primes.

Implement the Sieve of Eratosthenes in a Python program and find all the primes under 10000.