The Sieve of Eratosthenes

In this post we are going to investigate an ancient but highly effective algorithm known as the Sieve of Eratosthenes. This method, named after the Greek mathematician Eratosthenes (276 BC – 194B), is a simple and efficient way to find all prime numbers up to a specified integer. Let’s explore how it works!

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an algorithm that allows us to find all prime numbers up to any given limit. It does this by iteratively marking the multiples of each prime number starting from 2. The unmarked numbers that remain are prime numbers.

Step-by-Step Explanation

Let’s break down the process:

Step 1: Create a List of Numbers: Start by listing all the numbers from 2 to the desired upper limit. For example, if we want to find all prime numbers up to 100, we would list the numbers from 2 to 100. Imagine that all these numbers are in a large sieve. Progressively, the non primary numbers will be removed as they will “pass through” the sieve (see steps 2, 3 and 4)!

Step 2: Start with the First Number: The first number in the list is 2, which is a prime number. We will keep it (in our sieve) and eliminate all its multiples (i.e., 4, 6, 8, etc.) from the list because they are not prime.

Step 3: Move to the Next Unmarked Number: The next unmarked number is 3, which is also a prime number. We’ll keep it and eliminate all its multiples (i.e., 6, 9, 12, etc.) from the list.

Step 4: Repeat the Process: Continue this process with the next unmarked number, which is 5. Keep it and eliminate all its multiples. Repeat this process until you’ve gone through all the numbers in the list.

Step 5: Identify the Prime Numbers: The numbers that remain unmarked in the list are prime numbers.

Python Implementation

Here is a Python function that implements the Sieve of Eratosthenes algorithm:

Visual Representation

The following code uses Python Turtle to create a visual representation of the Sieve of Eratosthenes. The numbers in magenta are non primary numbers whereas the numbers in white are “left in the sieve” and are hence primary numbers:

Did you Know?

Eratosthenes was born in 276 BCE in Cyrene, a Greek city in modern-day Libya. He was a man of many talents and interests, which led him to study in various fields. He was a poet, an astronomer, a geographer, and a mathematician. He is especially known for his work on prime numbers (The Sieve of Eratosthenes) and for being the first person to accurately calculate the Earth’s circumference.