Sieve of Eratosthenes
The Sieve of Eratosthenes is a simple and ancient method to find all prime numbers up to a given number. It was invented by a Greek mathematician named Eratosthenes over 2,000 years ago.
Instead of checking each number one by one, this method removes (or "sieves out") all composite numbers, leaving only the prime numbers behind.
What is Sieve of Eratosthenes - Class 4 Maths (Factors and Multiples)?
The Sieve of Eratosthenes is a step-by-step method to find all prime numbers up to any given number. It works by crossing out the multiples of each prime number, starting from 2.
Steps:
- Write all numbers from 2 to the given number in a grid.
- Circle 2 (the first prime). Cross out all multiples of 2 (4, 6, 8, 10, ...).
- Circle the next uncrossed number (3). Cross out all multiples of 3 (6, 9, 12, 15, ...).
- Circle the next uncrossed number (5). Cross out all multiples of 5.
- Continue this process. All circled (uncrossed) numbers are prime.
Sieve of Eratosthenes Formula
Cross out multiples of 2, then 3, then 5, then 7, ... The remaining numbers are prime.
Solved Examples
Example 1: Example 1: Sieve from 1 to 30
Problem: Use the Sieve of Eratosthenes to find all prime numbers from 1 to 30.
Solution:
Step 1: Write numbers from 2 to 30. (1 is neither prime nor composite, so skip it.)
Step 2: Circle 2. Cross out multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
Step 3: Circle 3 (next uncrossed). Cross out multiples of 3: 9, 15, 21, 27 (6, 12, 18, 24, 30 already crossed).
Step 4: Circle 5 (next uncrossed). Cross out multiples of 5: 25 (10, 15, 20, 30 already crossed).
Step 5: All remaining uncrossed numbers are prime.
Answer: Prime numbers from 1 to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Example 2: Example 2: Sieve from 1 to 20
Problem: Find all prime numbers up to 20 using the Sieve.
Solution:
Step 1: Numbers: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Step 2: Circle 2, cross out: 4, 6, 8, 10, 12, 14, 16, 18, 20
Step 3: Circle 3, cross out: 9, 15
Step 4: Circle 5 (nothing new to cross out below 20 that is not already crossed)
Step 5: Remaining uncrossed: 7, 11, 13, 17, 19
Answer: Prime numbers up to 20: 2, 3, 5, 7, 11, 13, 17, 19 (8 primes)
Example 3: Example 3: Count Prime Numbers up to 50
Problem: How many prime numbers are there between 1 and 50?
Solution:
Step 1: Apply the sieve — cross out multiples of 2, 3, 5, and 7.
Step 2: Remaining primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Answer: There are 15 prime numbers between 1 and 50.
Example 4: Example 4: Identify Crossed-Out Numbers
Problem: In the Sieve of Eratosthenes up to 30, which numbers are crossed out when we remove multiples of 3?
Solution:
Step 1: Multiples of 3 up to 30 = 3, 6, 9, 12, 15, 18, 21, 24, 27, 30
Step 2: 3 itself is prime (we circle it, not cross it out).
Step 3: Among 6, 9, 12, 15, 18, 21, 24, 27, 30 — some (like 6, 12, 18, 24, 30) are already crossed as multiples of 2.
Step 4: New numbers crossed out at this step: 9, 15, 21, 27
Answer: The numbers newly crossed out for multiples of 3 are 9, 15, 21, 27.
Example 5: Example 5: Why Stop at a Certain Prime?
Problem: When using the Sieve up to 50, why do we only need to cross out multiples of 2, 3, 5, and 7?
Solution:
Step 1: We only need to cross out multiples of primes up to the square root of 50.
Step 2: The square root of 50 is approximately 7.07.
Step 3: So we only need to cross out multiples of primes up to 7, which are: 2, 3, 5, 7.
Answer: After crossing out multiples of 2, 3, 5, and 7, all remaining uncrossed numbers up to 50 are guaranteed to be prime.
Example 6: Example 6: Word Problem
Problem: Priya wrote numbers from 1 to 40 on a chart. She crossed out all multiples of 2 (except 2) and all multiples of 3 (except 3). How many numbers are still uncrossed?
Solution:
Step 1: Start with numbers 2 to 40 (39 numbers). Keep 1 out since it is neither prime nor composite.
Step 2: Multiples of 2 crossed: 4, 6, 8, 10, ..., 40 = 19 numbers crossed
Step 3: Multiples of 3 not yet crossed: 9, 15, 21, 27, 33, 39 = 6 more crossed
Step 4: Total crossed = 19 + 6 = 25
Step 5: Remaining = 39 − 25 = 14 uncrossed numbers
Answer: 14 numbers remain uncrossed (including 2 and 3 themselves).
Example 7: Example 7: Finding Primes Between Two Numbers
Problem: Use the sieve to find prime numbers between 20 and 40.
Solution:
Step 1: List: 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
Step 2: Cross out even numbers (multiples of 2): 22, 24, 26, 28, 30, 32, 34, 36, 38, 40
Step 3: Cross out remaining multiples of 3: 21, 27, 33, 39
Step 4: Cross out remaining multiples of 5: 25, 35
Step 5: Remaining: 23, 29, 31, 37
Answer: Prime numbers between 20 and 40: 23, 29, 31, 37
Example 8: Example 8: Building a Number Grid
Problem: Rahul has a 5 × 5 grid with numbers 1 to 25. Apply the Sieve and list the primes.
Solution:
| 1 | 2 | 3 | 5 | |
| 7 | ||||
| 11 | 13 | |||
| 17 | 19 | |||
| 23 |
Answer: Primes from 1 to 25: 2, 3, 5, 7, 11, 13, 17, 19, 23 (9 primes)
Example 9: Example 9: Sieve Up to 10
Problem: Find all prime numbers up to 10 using the Sieve.
Solution:
Step 1: Write: 2, 3, 4, 5, 6, 7, 8, 9, 10
Step 2: Circle 2. Cross out 4, 6, 8, 10.
Step 3: Circle 3. Cross out 9.
Step 4: Circle 5 and 7 (no more multiples to cross).
Answer: Prime numbers up to 10: 2, 3, 5, 7
Key Points to Remember
- The Sieve of Eratosthenes is a method to find all prime numbers up to a given limit.
- Start by crossing out multiples of the smallest prime (2), then 3, then 5, and so on.
- Numbers that remain uncrossed are prime.
- You only need to sieve multiples of primes up to the square root of the limit.
- The number 1 is skipped because it is neither prime nor composite.
- This method is much faster than checking each number individually.
Practice Problems
- Use the Sieve of Eratosthenes to find all prime numbers between 1 and 40.
- How many composite numbers are there between 1 and 25?
- After crossing out multiples of 2, 3, and 5 from numbers 1 to 50, how many numbers remain uncrossed?
- Aditi made a number grid from 1 to 30. She crossed out multiples of 2. How many numbers remain uncrossed (including 2)?
- Use the Sieve to find all prime numbers between 40 and 60.
- Which is the largest prime number less than 50?
- If you use the Sieve up to 100, what is the largest prime whose multiples you need to cross out?
Frequently Asked Questions
Q1. What is the Sieve of Eratosthenes?
It is a step-by-step method to find all prime numbers up to a certain limit. You write all numbers in a grid and cross out multiples of each prime starting from 2. The uncrossed numbers are the primes.
Q2. Who invented the Sieve of Eratosthenes?
It was invented by Eratosthenes, a Greek mathematician, around 240 BC. He was also the first person to calculate the circumference of the Earth.
Q3. Why do we skip 1 in the sieve?
The number 1 is neither prime nor composite because it has only one factor (itself). The sieve is used to find primes, so 1 is not included.
Q4. Why do we start crossing out from 2?
2 is the smallest prime number. Its multiples (4, 6, 8, ...) are all composite, so they are crossed out first. Then we move to 3, 5, 7, and so on.
Q5. When do we stop the sieve process?
You stop when you have crossed out multiples of all primes up to the square root of the limit. For example, for numbers up to 50, you only need to cross out multiples of 2, 3, 5, and 7 (since the square root of 50 is about 7).
Q6. Can the sieve find primes beyond 100?
Yes. The sieve works for any range. However, for very large numbers, the grid becomes very big. In Class 4, the sieve is typically used for numbers up to 100.
Q7. How many primes are there from 1 to 100?
There are 25 prime numbers from 1 to 100. They are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Q8. Why is this method called a sieve?
A sieve is a tool with holes used to filter things. Just like a kitchen sieve separates large pieces from small ones, this method filters out composite numbers and lets only prime numbers pass through.
Q9. Is the Sieve of Eratosthenes in the NCERT Class 4 syllabus?
Yes. The sieve is introduced in Class 4 as a method to identify prime numbers. It is part of the Factors and Multiples chapter.
