Understanding the Sieve of Eratosthenes: A Step-by-Step Guide

In this guide, we'll explore the Sieve of Eratosthenes, an ancient algorithm for finding all prime numbers up to a specified integer. We'll break down the process step-by-step and provide practical examples to make it easy for you to understand.
By Taylor

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is a simple and efficient way to find all prime numbers up to a certain number, say 30. A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, a prime number has exactly two distinct positive divisors: 1 and itself.

How Does It Work?

Here’s a step-by-step breakdown of the Sieve of Eratosthenes:

  1. Create a List: Start by writing down all the numbers from 2 up to the maximum number you want (let’s say 30).

    2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

  2. Start with the First Prime (2): Circle the first number (2). This is our first prime number.

  3. Eliminate Multiples of 2: Cross out every multiple of 2 in the list (4, 6, 8, etc.).

    2, 3, ~4~, 5, ~6~, 7, ~8~, ~9~, ~10~, 11, ~12~, 13, ~14~, ~15~, ~16~, 17, ~18~, 19, ~20~, ~21~, ~22~, 23, ~24~, ~25~, ~26~, ~27~, ~28~, 29, ~30~

  4. Move to the Next Number (3): The next number that is not crossed out is 3. Circle 3 as it is prime.

  5. Eliminate Multiples of 3: Cross out every multiple of 3 (6, 9, 12, etc.).

    2, 3, ~4~, 5, ~6~, 7, ~8~, ~9~, ~10~, 11, ~12~, 13, ~14~, ~15~, ~16~, 17, ~18~, 19, ~20~, ~21~, ~22~, 23, ~24~, ~25~, ~26~, ~27~, ~28~, 29, ~30~

  6. Continue the Process: Repeat this process with the next number that hasn’t been crossed out (which is 5), then 7, and so on.

  7. Stop When You Reach the Square Root: You can stop once you’ve processed numbers up to the square root of your maximum number (for 30, that’s roughly 5.47, so we only need to check 2, 3, and 5).

  8. List the Remaining Circled Numbers: The numbers that remain uncrossed are prime numbers.

    Remaining numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Practical Example

Let’s apply the Sieve of Eratosthenes to find all prime numbers up to 50:

  1. Write down the numbers:
    2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50

  2. Circle 2, then cross out all multiples of 2:
    2, 3, ~4~, 5, ~6~, 7, ~8~, ~9~, ~10~, 11, ~12~, 13, ~14~, ~15~, ~16~, 17, ~18~, 19, ~20~, ~21~, ~22~, 23, ~24~, ~25~, ~26~, ~27~, ~28~, 29, ~30~, ~31~, ~32~, ~33~, ~34~, ~35~, ~36~, 37, ~38~, ~39~, ~40~, 41, ~42~, ~43~, ~44~, ~45~, ~46~, ~47~, ~48~, ~49~, ~50~

  3. Circle 3 and cross out multiples of 3:
    2, 3, ~4~, 5, ~6~, 7, ~8~, ~9~, ~10~, 11, ~12~, 13, ~14~, ~15~, ~16~, 17, ~18~, 19, ~20~, ~21~, ~22~, 23, ~24~, ~25~, ~26~, ~27~, ~28~, 29, ~30~, ~31~, ~32~, ~33~, ~34~, ~35~, ~36~, 37, ~38~, ~39~, ~40~, 41, ~42~, ~43~, ~44~, ~45~, ~46~, ~47~, ~48~, ~49~, ~50~

  4. Circle 5 and cross out multiples of 5:
    2, 3, ~4~, 5, ~6~, 7, ~8~, ~9~, ~10~, 11, ~12~, 13, ~14~, ~15~, ~16~, 17, ~18~, 19, ~20~, ~21~, ~22~, 23, ~24~, ~25~, ~26~, ~27~, ~28~, 29, ~30~, ~31~, ~32~, ~33~, ~34~, ~35~, ~36~, 37, ~38~, ~39~, ~40~, 41, ~42~, ~43~, ~44~, ~45~, ~46~, ~47~, ~48~, ~49~, ~50~

  5. Continue until reaching 7 and 8, then stop. The remaining circled numbers will be:
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Conclusion

The Sieve of Eratosthenes is a powerful tool for finding prime numbers efficiently. With this method, you can easily determine all the prime numbers up to any integer. Try it on different numbers and see how quickly you can find primes! Happy sieving!