How to use sieve of eratosthenes?
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
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.
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.
For e.g. 7 has only two factors 1 and 7 itself
For e.g. 6 has more than two factors which are 1,2, 3, and 6.
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.
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.
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:
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.
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.
- Generate numbers from 2 to T (2 is the smallest prime).
- Traverse from smallest prime number which is num = 2.
- Eliminate or mark all the multiples of num (as 0 or -1) which are lesser than or equal to T.
- Update the value of num to the immediate next prime number.
Also read: How to Find Prime Numbers?
In Mathematics, there are various methods to find the prime and composite numbers such as factorisation and division methods. But in the case of the Sieve of Eratosthenes method, it is easy to list down the prime numbers among a set of numbers in a quick way. Class 6 students can learn this method here and excel in it.
Before we proceed to learn about the Sieve of Eratosthenes method, let us first learn the definitions of prime and composite numbers.
The numbers apart from 1, whose only factors are 1 and the number itself, are known as prime numbers.
For example, 2 has only two factors: 1 and 2. Apart from that, 2 is not evenly divisible by any other factor. In the same way, 3, 5, 11, 17, etc., are primes.
The numbers that have more than two factors are called composite numbers. Therefore, the composite numbers are evenly divisible by two or more factors.
For example, 6 is a composite number because it has a total of four factors, i.e. 1, 2, 3, and 6. Hence, 6 is exactly divisible by all its factors.
Now here we are going to encircle the prime numbers from 1 to 100 using the Sieve of Eratosthenes method. As we have already discussed the prime and composite numbers above, therefore, it will be more convenient to find the difference between them.
The steps involved in separating the prime numbers from 1 to 100 are as follows:
Therefore, we have concluded that all the encircled numbers are prime numbers and all the crossed numbers are composite numbers. So, the prime numbers from 1 to 100 are:
Hence, the Sieve of Eratosthenes method is completed.
Q.1: Find if 101 is a prime number or not.
Solution: 101 is divisible by only two numbers, 1 and 101. Therefore, 101 is a prime number.
Q.2: What are all prime numbers less than 20. (Use the Sieve of Eratosthenes method).
Solution: Let us first write the numbers from 1 to 20.
Therefore, the required prime numbers between 1 to 20 are 2, 3, 5, 7, 11, 13, 17 and 19.
Q.3. Express the number 21 as the sum of three prime numbers.
Solution: 21 can be written as the sum of three prime numbers:
21 = 3 + 5 + 13
Where 3, 5 and 13 are prime numbers.
