Sieve of Eratosthenes: Method, History & Examples
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.
![]() |
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.
![]() |
The next prime is 3, so multiples of 3 can be taken out.
![]() |
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.
![]() |
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.
![]() |
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
![]() |
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.
![]() |
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.
This simple algorithm was an important tool that made the process of discovering prime numbers for ancient Greeks without computers (or Google) much, much easier. But here's the ironic twist to that statement: Eratosthenes' sieve has an intimate connection with modern computers! In the 1950s and early 1960s, when computers were first being developed, scientists and engineers looked at sieves like Eratosthenes' as a benchmark for computer performance. Now that computers are ubiquitous, prime numbers and sieves are used in the field of cryptography to encrypt and protect your data online.
However, it's important to note that the sieve had little practical application in the ancient world. While incredibly important to the development of pure mathematics, interest in these types of abstract inquiries seemingly fell out of vogue after the Hellenistic period. This was due in large part to the influence of the Roman empire that ended the Hellenistic Age and encouraged practical, physical sciences like engineering.
Lesson Summary
Eratosthenes made many important contributions to science and mathematics. His prime number sieve provided a simple way for Greek mathematicians (and frustrated modern students!) to find all prime numbers between any two integers. He lived and worked in the Hellenistic Age, a multicultural age where Greek culture spread throughout Eurasia and the exchange of ideas lead to developments like his famous sieve.
To unlock this lesson you must be a Study.com Member.
Create your account
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
![]() |
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.
![]() |
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.
This simple algorithm was an important tool that made the process of discovering prime numbers for ancient Greeks without computers (or Google) much, much easier. But here's the ironic twist to that statement: Eratosthenes' sieve has an intimate connection with modern computers! In the 1950s and early 1960s, when computers were first being developed, scientists and engineers looked at sieves like Eratosthenes' as a benchmark for computer performance. Now that computers are ubiquitous, prime numbers and sieves are used in the field of cryptography to encrypt and protect your data online.
However, it's important to note that the sieve had little practical application in the ancient world. While incredibly important to the development of pure mathematics, interest in these types of abstract inquiries seemingly fell out of vogue after the Hellenistic period. This was due in large part to the influence of the Roman empire that ended the Hellenistic Age and encouraged practical, physical sciences like engineering.
Lesson Summary
Eratosthenes made many important contributions to science and mathematics. His prime number sieve provided a simple way for Greek mathematicians (and frustrated modern students!) to find all prime numbers between any two integers. He lived and worked in the Hellenistic Age, a multicultural age where Greek culture spread throughout Eurasia and the exchange of ideas lead to developments like his famous sieve.
To unlock this lesson you must be a Study.com Member.
Create your account
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
Unlock Your Education
See for yourself why 30 million people use Study.com
Become a Study.com member and start learning now.
Become a MemberAlready a member? Log In
BackSieve of Eratosthenes Method & History | What is the Sieve of Eratosthenes?
Related Study Materials
- General Science Lessons
- TExES Science of Teaching Reading (293): Practice & Study Guide
- Next Gen NCLEX-PN Study Guide & Practice
- Next Gen NCLEX-RN Study Guide & Practice
- TExES Core Subjects EC-6 (391): Practice & Study Guide
- General Sea Creatures
- General Pre-Historic History
- General Sea Mammals
- About the Next Gen NCLEX
- Factors Affecting Reading Development
- How to Pick Your Homeschool Curriculum
- Role of Student Support in Open & Distance Learning
- TExES Principal Exam Redesign (068 vs. 268)
- Teacher Salary by State
- ESL Resource Guide for Teachers
- What is a Homeschool Co-op?
- How to Start Homeschooling Your Children
Latest Courses
- Victimization Consequences: Emotional, Psychological & Social
- Political Satire: Definition & Examples
- Niels Bohr: Biography, Atomic Theory & Discovery
- Aymara People: Language, Culture & Religion
- Next Gen NCLEX Question Type: Drag and Drop
- What is Passover? - Definition, Story, Traditions & Significance
- Red Fox Scientific Name & Habitat | Are Foxes Nocturnal?
- Quiz & Worksheet - Mestizaje Overview
- Quiz & Worksheet - Hittite Government, Laws & Economy
- Quiz & Worksheet - Paleo Indian Culture & Artifacts
- Quiz & Worksheet - Witchcraft, Oracles, and Magic Among the Azande Synopsis
- Flashcards - Real Estate Marketing Basics
- Flashcards - Promotional Marketing in Real Estate
- Active Learning | Definition & Strategies for Teachers
- Rubrics | Rubric Definition and Types
Latest Lessons
- Principles of Physical Science: Certificate Program
- Praxis Family & Consumer Sciences (5122): Practice & Study Guide
- Western Civilization Textbook
- Principles of Health for Teachers: Professional Development
- Introduction to Psychology: Tutoring Solution
- High School Geometry: Properties of Triangles
- The Rise of the Roman Republic: Tutoring Solution
- Quiz & Worksheet - Radians and Degrees
- Quiz & Worksheet - Exterior Angle Theorem
- Quiz & Worksheet - Fundamentals of Marksmanship
- Quiz & Worksheet - Headright System
- Quiz & Worksheet - History & Characteristics of Carolingian Art
Popular Courses
- Choctaw Tribe: History & Facts
- Water Quality & Water Supply: Definition & Purpose
- How to Use the GED RLA Prep Course
- MTTC Test Prep Product Comparison
- National Associations for Speech & Speech Education
- How to Register for the OAE Test
- ISEE Test Costs
- FTCE Math 5-9: Passing Score
- How to Register for the OAE Test
- Romeo and Juliet Act 4 Lesson Plan
- MTEL Test Centers
- Writing Prompts for High School
Popular Lessons
Math
Social Sciences
Science
Business
Humanities
Education
History
Art and Design
Tech and Engineering
- Tech and Engineering - Videos
- Tech and Engineering - Quizzes
- Tech and Engineering - Questions & Answers
Health and Medicine
- A prime number is a positive integer that has no factors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, .... We denote by pi(n) the number of primes that are less than or eq
- What did Eratosthenes accomplish?
- Why does the Sieve of Eratosthenes work?
- Who discovered prime and composite numbers?
- What were Eratosthenes two major contributions to ocean exploration?
- What is the importance of the Sieve of Eratosthenes?
- What is the purpose of Eratosthenes' experiment?
- What has the Sieve of Eratosthenes done for the world?
- What is the asymptotic performance of the Sieve of Eratosthenes?
- How accurate is the Sieve of Eratosthenes?