Step-by-Step Guide: Applying the Sieve to Identify Primes
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 Explained: Find Prime Numbers 1 to 100
1. What is the Sieve of Eratosthenes method?
The Sieve of Eratosthenes is an efficient method for finding all prime numbers up to a certain limit. It repeatedly marks the multiples of each prime number, starting from 2, as composite numbers. This process simplifies identifying prime numbers in number theory.
2. What is the Sieve of Eratosthenes 1 to 100?
The Sieve of Eratosthenes from 1 to 100 finds all prime numbers between 1 and 100 by marking multiples of each discovered prime. This math algorithm lists every prime in this range, such as 2, 3, 5, and more, for easier understanding.
3. What is the most efficient algorithm to find prime numbers?
The Sieve of Eratosthenes is one of the most efficient algorithms to find all primes up to a number. It avoids redundancy by removing composite numbers quickly, making it useful for finding prime numbers efficiently in mathematics.
4. What is the sieve formula?
The sieve formula generally refers to the principle behind the Sieve of Eratosthenes, which works by striking out multiples of each found prime. This process continues up to the square root of the highest number in the algorithm.
5. How does the Sieve of Eratosthenes work step by step?
To use the Sieve of Eratosthenes, you:
- List numbers up to your limit
- Mark multiples of each prime as composite
- Continue steps until only primes remain
6. Why is the Sieve of Eratosthenes important in mathematics?
The Sieve of Eratosthenes is important because it provides a simple and effective way to find prime numbers, which are basic building blocks in mathematics. Understanding primes helps with cryptography, number theory, and problem-solving.
7. Who invented the Sieve of Eratosthenes?
The Sieve of Eratosthenes was invented by the ancient Greek mathematician Eratosthenes of Cyrene. This mathematician lived around 276–194 BC and contributed significantly to the history of mathematics, especially with this prime-finding technique.
8. Can the Sieve of Eratosthenes be used for large numbers?
The Sieve of Eratosthenes is efficient for moderate-sized numbers, but for very large numbers, memory use increases. For huge ranges, advanced sieve methods like the segmented sieve are used to identify prime numbers effectively.
9. What are the limitations of the Sieve of Eratosthenes?
The main limitations are memory and computation. The Sieve of Eratosthenes uses a lot of memory for large ranges and may not be practical beyond millions. Its simplicity is best for small to medium lists of prime numbers.
10. What is a composite number in the Sieve of Eratosthenes?
A composite number in the Sieve of Eratosthenes is any number greater than 1 that is not prime. These numbers have divisors other than 1 and themselves, so they get marked and removed during the sieve process.
