Eratosthenes & The Sieve

Mathematics has beauty and romance. It’s not a boring place to be….It’s an extraordinary place; it’s worth spending time there—Marcus du Sautoy

era-2.pngMath can be fun. This statement may bring shrieks to students throughout the blogosphere, but hear me out. Thanks to a mathematician named Eratosthenes, a portion of math has gotten easier and indeed more enjoyable.

The ancient Greek savant developed an algorithm to quickly and easily indentify prime numbers. His method is referred to as the Sieve Of Eratosthenes. A Crow’s View finds it interesting on many different levels.

Eratosthenes lived from 276-194 BCE. He hailed from the Greek colony Cyrene in what is now present day Libya. His achievements include calculating the Earth’s circumference (the first to do so), founded scientific chronology, and was chief librarian at the Library of Alexandria. He is even credited with inventing the concept of Leap Day.

In his day Eratosthenes was renowned for his intelligence. He was a man of many talents and excelled in many fields. Contemporaries often referred to him as Beta, meaning second, or Pentathlos; referring to a person who is an “all-round athlete who was not the first” place finisher*. These nicknames may have been a pejorative in his lifetime, but they do speak to his intellect and ingenuity.

An example of Eratosthenes’ genius is his creation of the sieve. His mathematical discovery allows users to quickly separate composite and prime numbers without having to use division.

The way the sieve works is by making an array of numbers. For this illustration we will use a range of 20. Start with the number two and then add all the numbers in the array.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

After the array is set, start with the first number on the list—the two (2). It is the first prime number, then eliminate any number that it can be divided into. Since Eratosthenes sieve doesn’t require division, the easiest way to find any composite number is to count two spaces to the right and then cross out that number. Then move right two more spaces and discard that digit; repeat this step till you reach the end of the array.

For this example, the composite numbers will be underlined and prime numbers left unchanged. The first iteration will return this result:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Continue the sifting process by moving to the next prime number in the array, the three (3). Start by counting three spots to the right, then underline that digit. If a number is already eliminated (underlined), then continue on to the next number in the series by counting three more spaces to the right. Do this until you reach the end of the array. The new iteration is below.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The three (3) sifts out the nine (9) and the 15, leaving only prime numbers. This is a small array, so each iteration after the three (3) will return the same result, so we are done. But if you want to be sure that all of the prime numbers were discovered, continue this process by going to the next prime number in the series. Skip any number that is underlined.

The five (5) will be the next starting point. With the five (5), it is the same process, but this time count five spots to the right, then either underline or skip that number (if already underlined). Continue the process to the end of the array. To check for accuracy repeat the same steps as above. Just remember to count to the right the same number of spaces as the value of the number you start with. 

After running the remaining numbers in the series, you will quickly see that 2, 3, 5, 7, 11, 13, 17 and 19 are left unchanged. These are the prime numbers in our array of 20.

The sieve may seem simplistic, but that is not necessarily the case. It uses a set of algorithms and multiple iterations to methodically sort out prime numbers from the composites. To see the sieve of Eratosthenes at work, an internet search will offer some great examples. Some sites have animated sieves that quickly identify all prime and composite numbers in a large scale array.

Eratosthenes’ method for identifying prime numbers really is quite ingenious. The sieve was ahead of its time. In fact, it is still relevant more than 2000 years after its creation, and it does what modern science doesn’t do. It makes math fun.

Eratosthenes

Smart Trick Method Article

Eratosthenes Bio

Eratosthenes Of Cyrene

History Of Eratosthenes

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s