|
Sieve of Eratosthenes |
10 points
The Sieve of Eratosthenes was created by the Greek polymath Eratosthenes, in the 3rd century BCE. The Sieve provides a method of finding prime numbers. Here is how it works. Let's find the prime numbers from 2 up to 20. We start with 2, the smallest prime number. We keep 2 but eliminate all of its multiples:
2 3 4 5 6 7
8 9
10 11
12 13
14 15
16 17
18 19
20
We move on to 3. We keep 3 but eliminate its multiple (9) that is still present:
2 3 5 7 9 11 13 15 17 19
We move on to 5. We keep 5 but eliminate its multiple (15):
2 3 5 7 11 13 15 17 19
We move on to 7. We keep 7 but it has no multiples to eliminate.
We move on to 11. We keep 11 but it has no multiples to eliminate.
We move on to 13. We keep 13 but it has no multiples to eliminate.
We move on to 17. We keep 17 but it has no multiples to eliminate.
We move on to 19. We keep 19 but it has no multiples to eliminate.
Here is our final list of primes up to 20: 2 3 5 7 11 13 17 19.
In this program, we code up the Sieve of Eratosthenes. When complete, the program will be able to print all of the prime numbers up to an ending number that the user provides.
The video below shows a completed program being run.
Download Sieve.py as a starting point for the project. The file guides you towards completing the program.