How to Use the Sieve Of Eratosthenes to Find Prime Numbers Step by Step
The Sieve of Eratosthenes is used to identify prime numbers and composite numbers. We will discuss in detail the topic and find the prime numbers from 1 to 100. By the sieve of Eratosthenes, we have 25 prime numbers and 75 composite numbers between 1 to 100. Eratosthenes sieve method is the easiest way to find prime numbers from given many numbers.
There are 25 numbers between 1 to 100: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89 and 97
Eratosthenes Sieve Method
This method is used to identify the prime numbers from a group of natural numbers. In this method, first, we will identify all composite numbers. The remaining numbers are the prime numbers.
What is the Sieve of Eratosthenes?
Sieve of Eratosthenes is a method by which we can find prime numbers and composite numbers that are less than 10 million.
Sieve of Eratosthenes is also said to be an algorithm because it follows a set of operations.
Prime Numbers and Composite Numbers
Prime Numbers are those numbers that have only two factors 1 and themselves.
For e.g. 7 has only two factors 1 and 7 itself
Composite Numbers are those numbers that have more than two factors with 1 and themselves.
For e.g. 6 has more than two factors which are 1,2, 3, and 6.
Sieve of Eratosthenes Prime Numbers 1 - 100
Now we will learn how to find the first 25 prime numbers or prime numbers between 1 to 100 by Sieve of Eratosthenes. We write the number from 1 to 100 like this and follow the given steps:
Step 1: First we write all the natural numbers row-wise and column-wise like the given table.
Step 2: Cross the number 1 as it is not a prime or composite number.
Step 3: Now leave 2 and cross the multiples of 2 as all are composite numbers.
Step 4: Next leave 3 and cross the multiples of 3 as all are composite numbers.
Step 5: Again we will leave 5 and cross the multiple of 5 apart from 5 all are composite numbers.
Step 6: Now leave 7 and cross all multiples of 7.
At this step, we covered all number composite numbers. The rest numbers are prime.
The multiples of 2 from 1 to 100are 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.
The multiple of 3 from 1 to 100 are 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99.
The multiple of 4 from 1 to 100 are 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100.
The multiples of 5 are 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
The multiple of 6 from 1 to 100 are 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96.
The multiples of 7 from 1 to 100 are 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
The multiples of 8 are also multiples of 2 and 4.
The multiples of 9 are also multiples of 3.
The multiples of 10 are also multiples of 5.
The multiples of 11 are also multiples of 2,3,4,5,6,8,9.
Similarly, the multiples of 12, 13, 14 …, and 99 are marked when we marked the multiples of 2,3,4,5,6,7,8,9,10.
Therefore, we will mark all multiples of the numbers of 2 to the square root of 100 that is 10 and the rest will be prime numbers.
Prime Numbers Using Sieve of Eratosthenes
After finishing the process we will get all prime numbers between 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, and 97. There are 25 prime numbers between 1 to 100.
So this is the way to find prime number sieve by the Sieve of Eratosthenes.
Interesting Facts
2 is the smallest and only prime number that is even.
Every prime number except 2 is an odd number.
Developer of Sieve Eratosthenes method Greek Mathematician Eratosthenes is also known as the Father of Geography.
Solved Examples
Q1. Find 99 is a prime or composite number.
Solution. Factors of 99 are 1,3,9 and 11. It has more than two factors except 1 and 99. Therefore, it’s a Composite number.
Q2. Is 37 is a prime number.
Solution: Factors of 37 are 1 and 37, therefore it’s a prime number because it has only two factors 1 and itself.
Q3. Write all Prime numbers between 1 to 50 by the Sieve Eratosthenes method.
Solution: First we prepare the table to find the prime numbers between 1 to 50 and follow the following steps:
First, we write all the natural numbers row-wise and column-wise like the given table.
Cross the number 1 as it is not a prime nor composite number.
Now color the 2 and cross the multiples of 2 as all are composite numbers.
Next color the 3 and cross the multiples of 3 as all are composite numbers.
Again, we will color the 5 number and cross the multiple of 5 apart from 5 all are composite numbers.
Now color the number 7 and cross all multiples of them.
Continue the process till all numbers get color and cross.
Hence, there are 15 prime numbers between 1 to 50, they are 2,3,5,7,11,13,17,19,23,29,31,37,41,43 and 47.
Key Features
The Prime numbers from 1 to 100 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, and 97.
Number of composite numbers is 75.
The number of prime numbers from 1 to 100 is 25.
Practice Problem
1. Find the greatest prime number less than 120.
Answer: 113.
2. Find the sum of the two greatest prime numbers less than 110.
Answer: 226.
FAQs on Sieve Of Eratosthenes Prime Number Finding Method
1. What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is an efficient algorithm used to find all prime numbers up to a given number n. It works by systematically eliminating the multiples of each prime number starting from 2.
- Write all numbers from 2 to n.
- Mark 2 as prime and eliminate its multiples.
- Move to the next unmarked number and repeat.
- Continue until you reach √n.
2. How does the Sieve of Eratosthenes work step by step?
The Sieve of Eratosthenes works by repeatedly marking the multiples of each prime number as composite.
- Step 1: List numbers from 2 to n.
- Step 2: Start with 2 (first prime).
- Step 3: Eliminate all multiples of 2.
- Step 4: Move to the next unmarked number (3) and eliminate its multiples.
- Step 5: Continue this process up to √n.
3. Why do we stop at √n in the Sieve of Eratosthenes?
We stop at √n because any composite number greater than √n must have a factor smaller than or equal to √n. If a number n = a × b, then at least one of the factors a or b is ≤ √n. Therefore, once all multiples up to √n are removed, the remaining numbers must be prime.
4. Can you give an example of the Sieve of Eratosthenes up to 30?
Using the Sieve of Eratosthenes up to 30 gives the prime numbers less than or equal to 30.
- Start with numbers 2 to 30.
- Remove multiples of 2: 4, 6, 8, ..., 30.
- Remove multiples of 3: 6, 9, 12, ..., 30.
- Remove multiples of 5: 10, 15, 20, 25, 30.
5. What is the time complexity of the Sieve of Eratosthenes?
The time complexity of the Sieve of Eratosthenes is O(n log log n). This efficiency comes from eliminating multiples of primes in a structured way rather than checking each number individually. It is much faster than trial division for generating all prime numbers up to n.
6. What is the space complexity of the Sieve of Eratosthenes?
The space complexity of the Sieve of Eratosthenes is O(n). It requires an array or list of size n to mark numbers as prime or composite. This makes it memory-efficient for moderate values of n.
7. What is the difference between the Sieve of Eratosthenes and trial division?
The main difference is that the Sieve of Eratosthenes finds all primes up to n at once, while trial division checks each number individually for primality.
- Sieve: Time complexity O(n log log n).
- Trial division (per number): Up to O(√n).
- Sieve is better for generating many primes.
- Trial division is simpler for checking a single number.
8. What are the advantages of the Sieve of Eratosthenes?
The Sieve of Eratosthenes is advantageous because it is fast and simple for generating prime numbers.
- Efficient time complexity O(n log log n).
- Easy to implement.
- Suitable for competitive exams and programming.
- Generates all primes up to n in one run.
9. What are the limitations of the Sieve of Eratosthenes?
The main limitation of the Sieve of Eratosthenes is its O(n) space requirement. For very large values of n, storing an array of size n can consume significant memory. In such cases, optimized versions like the Segmented Sieve are preferred.
10. Who invented the Sieve of Eratosthenes?
The Sieve of Eratosthenes was invented by the Greek mathematician Eratosthenes of Cyrene around the 3rd century BCE. He developed this algorithm to efficiently identify prime numbers, contributing significantly to early number theory.
