1. Initialization: Create a list of consecutive integers from 2 to the given integer. Initially, mark all numbers as prime.
2. Iteration:
* Start with the first number, 2. It's prime, so mark all its multiples (4, 6, 8, etc.) as non-prime.
* Move to the next unmarked number, 3. It's prime, so mark all its multiples (6, 9, 12, etc.) as non-prime.
* Continue this process for each unmarked number.
3. Result: The unmarked numbers in the list at the end are all the prime numbers up to the given integer.
Example:
Let's find all prime numbers up to 20 using the Sieve of Eratosthenes:
1. Initialization:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
2. Iteration:
* 2: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 3: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 5: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 7: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 11: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 13: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 17: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
* 19: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
3. Result: The prime numbers less than or equal to 20 are: 2, 3, 5, 7, 11, 13, 17, and 19.
Key Points:
* The Sieve of Eratosthenes is a simple and efficient method for finding prime numbers within a given range.
* It works by systematically eliminating composite numbers (numbers with more than two factors) from the list.
* You only need to iterate up to the square root of the given integer.
* This algorithm has been known for over 2000 years.