Sieve of Eratosthenes Method & History | What is the Sieve of Eratosthenes?

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.

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.

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.

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.

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.

Applications of the Sieve of Eratosthenes

The Sieve of Eratosthenes is good for quickly finding small primes. The sieve as a concept is one in which successive rounds of calculation eliminate unnecessary results, so there are some possible uses in programming and mathematics. Running the Sieve of Eratosthenes as a program is a popular way to benchmark computer performance. Euler incorporated the sieve into his proof for Riemann zeta function. Called the Euler's Sieve, the first number on each step is a prime, and it is multiplied to remove composite numbers. The next step begins with the next prime, and so on. As far as finding primes, the Sieve of Eratosthenes has fallen out of use. Modern computational methods are superior at finding new primes today, which are millions of digits long.

Lesson Summary

A prime number is a positive integer that only has 1 and itself as a factor. All other positive integers have some prime number as a factor, and in fact each of them has a unique set of prime factors. When searching for prime numbers, then, it can be assumed that all of the multiples of a prime number are not prime, and so they can all be removed without testing. For example, since 5 is a prime, all multiples of 5 (10, 15, 20, 25...) cannot be prime, so there is no need to spend time testing them. This method of weeding out non-primes is called the Sieve of Eratosthenes. This method was developed by Greek mathematician and writer Eratosthenes, who lived during the Hellenistic period, a time in Greek history of intense thought and invention and great cultural expansion. Eratosthenes, the director of the Great Library of Alexandria, developed this quick and easy method for finding primes.

The method is simple: Make a list of numbers between two integers, and then cross out all the multiples of primes. While it fell out of use quickly after the Hellenistic period, the sieve was still one of the best ways to find small primes or generate a list of them. Today's new primes are much too big, and the searches for them require so much computing power, that the Sieve of Eratosthenes is not really useful. However, it was helpful in the early days of modern computing, when the sieve, used as a program, made a good benchmark for computer performance.

Eratosthenes and His Sieve

One of the few extant depictions of Eratosthenes

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

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

The sieve working between 2 and 120

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

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

Sieve of Eratosthenes: Method, History & Examples

Table of Contents

What is the Sieve of Eratosthenes?

An Ingenious Technique

History of the Sieve of Eratosthenes