In this chapter we shall learn about below topics:
3.1 Introduction.
3.2 Working of the algorithm
3.3 Understanding using an example
3.4 Implementation
3.5 Output
3.1 Introduction:
Sieve Of Eratosthenes is one of the most simple and efficient algorithm to find the prime numbers for a given set of limit.
3.2 Working of the algorithm:
The working of algorithm is very simple.
Step 1: First we write down all the numbers from 2 to n.
Step 2: From the first prime number i.e “2”, we strike out / remove all the numbers that are divisible by 2 till “n”.
Step 3: Then go to the next prime number, now strike out the numbers that are divisible by the present prime number till the square of the present prime number.
Step 4: Repeat step 3, till you reach the end.
Step 5: You will get the list of all the prime numbers.
3.3 Understanding Sieve Of Eratosthenes using an example:
In this example, we need all the prime numbers from 2 to 30. Below with the help of the image, I have explained the above steps.
Step 1: Write down all the numbers from 2 to n.
Step 2: From the number “2”, strike out all the multiple of 2. Here we have represented strike out in red color.
Step 3: Then go to the next prime number, now strike out the numbers that are divisible by the present prime number till the square of the present prime number. Here the next prime is 3, it’s square is 9. Hence strike out all the numbers that are multiple of 3 till 9. As 6 is already striked out earlier, we strike out 9 now.
Repeat step 3, till we reach the end. We shall try one more pass.
Now the next prime is “5”, it’s square is 25. Strike out all the numbers that are multiple of 5 till 25. i.e strikeout “10”, “15”, “20”, “25”. As “10” and “20” are already striked out, strike out “15” and “25”
Finally we shall left with the below numbers.
3.4 Implementation in C++
To implement in C++, we take a Boolean array of size n and mark all the fields as true. Then we apply above steps, instead of striking out, we make the particular cell as false. Finally, we write down all the cell index is true.
#include <iostream>
using namespace std;
void sieve_of_eratosthenes(int n)
{
//take a boolean array to store which index is a prime number.
bool prime[n + 1];
// make all the cells as true.
for (int i = 2; i <= n; i++)
{
prime[i] = true;
}
// from the first prime number
for(int j = 2; j*j <= n; j++)
{
// check if the current index is a prime number, if yes, then
if(prime[j] == true)
{
//if yes, then make all the cless that are multiple of that index as false
for(int i = j*2; i <= n; i += j)
{
prime[i] = false;
}
}
}
cout<<" All the prime numbers from 2 to 30 is "<<endl;
// from the first prime number, print all the prime numbers.
for(int j = 2; j <= n; j++)
if(prime[j]) // if prime[j] is true, then it is a prime number. Print it
cout << j << " ";
}
int main()
{
// n is the max limit to find the list of prime numbers from
int n = 30;
sieve_of_eratosthenes(n);
return 0;
}
3.5 Output
2 3 5 7 11 13 17 19 23 29