Copyright

The Sieve of Eratosthenes: Explanation & Overview

Instructor: Richard Reid
In this lesson we will learn about the Eratosthenes' Sieve, how it works, and why Eratosthenes was significant to ancient science. Then when you're done, you'll be able to test your newfound knowledge with a quiz!

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

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 risk-free for 30 days

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support