Sieve Of Eratosthenes

Introduction:

Sieve Of Eratosthenes is one of the mose simple and efficient algorithm to find the prime numbers for a given set of limit.

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.

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.

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 pirticular 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;
}

Output

2 3 5 7 11 13 17 19 23 29

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

List Of Tutorials available in this website: