Copyright

Sieve of Eratosthenes: Method, History & Examples

Ryan Johnson, Richard Reid
  • Author
    Ryan Johnson

    Ryan has tutored high school and college level math and science for over a decade, and has taught in a classroom setting for more than two. He has a BA in Chemistry from Ferris State University, and an MA in Archaeology from the University of Kansas.

  • Instructor
    Richard Reid
Learn what the Sieve of Eratosthenes is. Discover how Eratosthenes developed this method of finding prime numbers and study applications of the sieve. Updated: 05/05/2022

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is a powerful concept that can be used to find many prime numbers with relative speed and ease. It works on a simple principle: Any multiple of a prime number cannot be a prime number. For example, since 3 is prime, 6, 9, 12, 15, and all other multiples of 3 cannot be prime numbers. When trying to identify primes between two given integers or while searching for new primes, all multiples of primes can be discounted before the search even begins. The Sieve of Eratosthenes works like a filter, removing the multiples of all previous primes from the list of numbers so that time is not spent testing them.

An Ingenious Technique

What's the best way to find all the prime numbers between one and two hundred? You can always count, double check, multiply, and divide until you get frustrated and look up the answer on the internet. Or you could use an ingenious technique that a Greek mathematician invented over two thousand years ago.

History of the Sieve of Eratosthenes

Eratosthenes was born around 276 BCE in Cyrene, Libya (his full name was Eratosthenes of Cyrene). This puts him at the early part of the Hellenistic period in Greek history, which extended from the death of Alexander the Great (323 BCE) to the defeat of Ptolemaic Egypt and the beginning of the Roman Empire (31 BCE). The Hellenistic period saw Greece's greatest geographic expansion, both in territory and in cultural influence, with a large swath of the Mediterranean, Egypt, parts of India, and Asia Minor either directly under Greek control or subject to influence by Greek language, arts, and culture. Alexandria, Egypt, established by Alexander himself around a century before Eratosthenes' birth, was the undisputed center of the Hellenistic world, and this is where Eratosthenes eventually lived, worked, and died.

Most of Eratosthenes' works have not survived. His works are mentioned by later mathematicians and historians, however. It is known that he worked as director of the Great Library of Alexandria, and that he wrote on astronomy, history, philosophy, and mathematics. He is credited for calculating the first accurate estimate for the circumference of the Earth, and also for the Sieve of Eratosthenes. Although the sieve is an excellent tool for finding smaller primes, its use is diminished as primes become larger and larger (though the sieve concept is still used). Today, new primes have millions of digits, and they are found using computational and probabilistic tests for primacy.

Using Eratosthenes' Method of Finding Prime Numbers

Compared to other methods of finding primes, the Sieve of Eratosthenes is fast and easy to use, especially when computers are not available. For the sieve itself, there is no division required, no multiplication, and no finding factors. Those things might all be done to test a candidate for a prime, but the sieve quickly eliminates numbers that are definitely not prime. The sieve concept relies on the fact that every number can be divided into factors, and then those factors can be divided if necessary, all the way down until only prime factors are left. This is called the prime factorization of a number, and it indicates that all non-prime numbers have a unique set of prime factors.

In other words, every non-prime number has a prime as a factor. After a prime number is identified, then, all of its multiples can automatically be assumed as non-prime. The Sieve of Eratosthenes is a method for removing them. As an example, one can look at all the prime numbers between 2 and 31. First, one can list all the numbers between 2 and 31:

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

The first prime number is 2, so all of the multiples of 2 can be removed from the list. This is also why 2 is the only even prime.

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31

The next prime is 3, so all multiples of 3 can be removed.

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31

The next prime is 5.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

The next prime is 7. There are no multiples of 7 in this list, and in fact there are none for 11, 13, or 17, either. Since the first multiple of 17 would be greater than 31, this list has been "sieved." All of the numbers in it are now prime, and this can be checked with division if necessary.

Example of the Method

A visual example can show how the sieve works and how it filters out non-primes. One can consider the primes between 1 and 50 and start with a list of all the numbers in question.


This is the list the that will be sieved for primes.

list of numbers to sieve for primes


1 is not a prime, so it can be removed. Then, the first prime is 2. All multiples of 2 (all even numbers) can be removed.


Removing the evens struck out half of the numbers from the beginning.

number list sieved for evens


The next prime is 3, so multiples of 3 can be taken out.


There are fewer multiples of 3. Some were already removed because they were even numbers.

list of numbers sieved for primes


Next, one can remove the multiples of 5. There are fewer of these to consider. Half of the multiples of any prime will be even, and they are spread further apart as the primes get bigger.


There are only a few numbers removed this round.

list of numbers sieved for multiples of 5


Finally, the multiples of 7 can be removed. This will complete the sieve for this range. The multiples of the next prime, 11, have already been removed. In fact, if this list were longer, the first number removed as a multiple of any prime above 7 would be 143 (11 times 13). This is how effective the sieve can be.


In this round, only a single number is removed.

list sieved for multiples of 7


Eratosthenes and His Sieve

One of the few extant depictions of Eratosthenes
era

Eratosthenes lived during a time of rich experimentation and intellectual curiosity. This Hellenistic Age (named after the Greek word for Greece, Hellas) saw the expansion of Greek science and philosophy across the western world. Scholars and scientists from all around congregated in new libraries and schools to debate, discuss, and learn from one another. Eratosthenes used many of these ideas (borrowing from the best of Greek, Egyptian, and Mesopotamian thinkers) as the basis for a great number of mathematical discoveries. One of these discoveries (or inventions, depending on your perspective), was the Sieve of Eratosthenes.

The Sieve of Eratosthenes is a mathematical tool that's used to discover all possible prime numbers between any two numbers. Eratosthenes was a brilliant Greek thinker who, among many other important discoveries and inventions, was deeply interested in mathematics. His best known contribution to mathematics is his sieve used to easily find prime numbers. A mathematical sieve is any pattern or algorithm that functions by 'crossing off' any potential numbers that don't fit a certain criteria. In our case, the sieve of Eratosthenes works by crossing off numbers that are multiples of a number that we already know are prime numbers. While this all sounds quite complicated, in practice it's quite simple.

The sieve working between 2 and 120
sieve

Refer to the image above to see Eratosthenes' sieve in action.

To start the process, you identify the smallest prime number on your list of integers; in this example, it's 2. Then, you cross off every multiple of two on your list because you know that if a number is divisible by two, it can't be a prime number. Then, you proceed to the next number that is not crossed out to find your next prime number. The reason this works is because if it's not crossed out then it's not divisible by any other smaller number. Now you cross off every number that is a multiple of this new integer; in this example, it's 3. You repeat this process until you've reached the end of your number set and you have a list of all the prime numbers contained within.

To unlock this lesson you must be a Study.com Member.
Create your account

Additional Info

An Ingenious Technique

What's the best way to find all the prime numbers between one and two hundred? You can always count, double check, multiply, and divide until you get frustrated and look up the answer on the internet. Or you could use an ingenious technique that a Greek mathematician invented over two thousand years ago.

Eratosthenes and His Sieve

One of the few extant depictions of Eratosthenes
era

Eratosthenes lived during a time of rich experimentation and intellectual curiosity. This Hellenistic Age (named after the Greek word for Greece, Hellas) saw the expansion of Greek science and philosophy across the western world. Scholars and scientists from all around congregated in new libraries and schools to debate, discuss, and learn from one another. Eratosthenes used many of these ideas (borrowing from the best of Greek, Egyptian, and Mesopotamian thinkers) as the basis for a great number of mathematical discoveries. One of these discoveries (or inventions, depending on your perspective), was the Sieve of Eratosthenes.

The Sieve of Eratosthenes is a mathematical tool that's used to discover all possible prime numbers between any two numbers. Eratosthenes was a brilliant Greek thinker who, among many other important discoveries and inventions, was deeply interested in mathematics. His best known contribution to mathematics is his sieve used to easily find prime numbers. A mathematical sieve is any pattern or algorithm that functions by 'crossing off' any potential numbers that don't fit a certain criteria. In our case, the sieve of Eratosthenes works by crossing off numbers that are multiples of a number that we already know are prime numbers. While this all sounds quite complicated, in practice it's quite simple.

The sieve working between 2 and 120
sieve

Refer to the image above to see Eratosthenes' sieve in action.

To start the process, you identify the smallest prime number on your list of integers; in this example, it's 2. Then, you cross off every multiple of two on your list because you know that if a number is divisible by two, it can't be a prime number. Then, you proceed to the next number that is not crossed out to find your next prime number. The reason this works is because if it's not crossed out then it's not divisible by any other smaller number. Now you cross off every number that is a multiple of this new integer; in this example, it's 3. You repeat this process until you've reached the end of your number set and you have a list of all the prime numbers contained within.

To unlock this lesson you must be a Study.com Member.
Create your account

Frequently Asked Questions

What is the Sieve of Eratosthenes method?

The Sieve of Eratosthenes works on the idea that the multiples of a prime number are themselves not prime. When searching for primes, then, all of the multiples of each prime can be crossed out. This eliminates many numbers that would otherwise have been tested for no reason, so it saves time.

How did the Sieve of Eratosthenes get its name?

The Sieve of Eratosthenes was named after a Greek man named Eratosthenes. Eratosthenes was a mathematician, philosopher, historian, and director of the Great Library of Alexandria. At some point, he was interested in finding prime numbers, and he came up with the idea of the sieve. The "sieve" is a filter that removes non-primes as one goes along a list of numbers.

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it now
Create an account to start this course today
Used by over 30 million students worldwide
Create an account