Sieve of Eratosthenes
This is a famous algorithm to find prime numbers that was already known in in the 3rd century BCE.
Here is how it works:
- You start with an empty list of already known primes.
- Starting with the number 2 and then for all following numbers:
- Check if the current number can be divided by any of the known primes without remainder
- If this is the case, the current number can not be prime and you continue with the next number.
- If all divisions with a preceding prime leave a remainder, the current number is prime as well and is added to the list of known primes.
- Check if the current number can be divided by any of the known primes without remainder
Use this algorithm to find the 100th prime number.
Hints
Python’s break and continue statements can be of great help in this task.