The "Sieve of Eratosthenes" is a strategy for finding prime numbers up to a certain value. Start with a list of integers 2 through n:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... nBeginning with the first value, keep it on the list, but remove all multiples of that value from the list. In this case, multiples of 2 include 4, 6, 8, etc.
2, 3, 5, 7, 9, 11, 13, 15, Proceed to the next item on the list. Keep it, but remove all multiples of that value from the list. Here, it's 3, so we keep the 3, but remove 6 (already gone), 9, 12 (already gone), 15, etc.
2, 3, 5, 7, 11, 13, Continuing the process, keep 5 but remove multiples of 5 (none present on this short list)... remove multiples of 7, multiples of 11, and so on.
Once all the factors of these integers have been removed, the only integers remaining are the primes.
Write a program prime_finder3.py that asks the user the maximum value of primes they'd like to consider, then create a list of integers and perform the Sieve of Eratosthenes algorithm on that list.
Sample interaction:
$ python 5-05c-prime_finder3.py
Enter highest prime value to find: 20
Prime candidates:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Applying sieve process...
Removing 4
Removing 6
Removing 8
Removing 10
Removing 12
Removing 14
Removing 16
Removing 18
Removing 20
Removing 9
Removing 15
Done sieving!
[2, 3, 5, 7, 11, 13, 17, 19]