Sieve of Eratosthenes

The name seems to be threatening right? On the contrary, Sieve of Eratosthenes is a technique developed by one of the brilliant Greek Mathematicians, Eratosthenes, to eliminate complex looping multiplications or divisions. This algorithm removes all the numbers that do not meet a specific criterion, hence works like a sieve. This is one of the most effective methods to find out all the prime numbers that are smaller than a given number(say n).

The Simple C++ implementation of Sieve of Eratosthenes to find all prime numbers smaller than a given number have been shown below:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void Seive(int n){
    vector<bool> isPrime(n+1, true); //initializing all the elements in the boolean vector as true
    int i, j;
    for(i=2; i*i<=n; i++){
        if (isPrime[i] == true){ //if the value is true then it is a prime number
            for(j=2*i; j<=n; j=j+i){
                isPrime[j] = false; //marking all the multiple of the current number as false
            }
        }
    } //all the values from 2 onwards that are prime reamins true
    for(i=2; i<=n; i++){
        if(isPrime[i] == true){
            cout<<i<<" "; //this will print all the prime numbers till n
        }
    }
}
//The main function will be written as follows
int main(){
    int n = 15;
    cout<<"All the prime numbers till "<< n <<" are as follows:"<<endl;
    Seive(n); //calling the Seive function to implement the algorithm
    return 0;
}

Output
All the prime numbers till 15 are as follows:
2 3 5 7 11 13

Explanation of Sieve of Eratosthenes Algorithm

Here in the program we have taken n = 15. This means that we have to print all the prime numbers that are less than or equal to 15. Starting the Sieve of Eratosthenes Algorithm, first we create a boolean array or vector of size 16 (n+1). Index will be from 0 to n that will be used as numbers from 0 to n. We will not touch 0 and 1. Starting from 2 we will take only the true value indexes inside the inner loop and and mark all their multiples false which are less than or equal to n.

So taking 2, we mark all its multiples (i.e., 4, 6, 8, 10, 12, 14, etc) as false, while boolean value of 2 remains true. Moving on to the next number i.e. 3, we mark all of its multiple(i.e, 6, 9, 12, 15) as false, but 3 will remain true. The next value comes will be 5 not 4 as 4 have been marked false because it is a multiple of 2. Next number will be 7 not 6 and so on.
In this way, we can see that only prime numbers will come inside the inner for loop. Rest composite numbers will be filtered out as there must be a smaller number than them whose multiple they are.

So, we will only come across numbers like 2, 3, 5, 7, etc which are prime. But, their multiple can never be a prime. Hence we are marking them as false or in analogy passing them out from the sieve.

This way all the composite numbers will be marked as false. What left out will be prime. So, we can print all these numbers and hence we have the required answer.

Optimized Version of Sieve of Eratosthenes Algorithm

If you look carefully, the multiple less than the square of the number are already marked as false. For example if i = 5, then multiples less than 25(i.e., 5^2) is already marked false as the numbers 10, 15 and 20 are already multiples of 2, 3 and 4. Therefore there is no need to iterate again through these numbers. Hence we can directly start the iteration form i^2(i.e., 25).

The logic is, the numbers less than i^2 must be in the form i*(i-1) or i*(i-2) or i*(i-3), etc. Right? If that’s the case then they must be a multiple of a number less than i that is (i-1) or (i-2) or (i-3), etc. So, they must have been marked false while we are making the multiples of numbers less than i. Hence, we can start directly from i^2.

The second optimization that we did is, we put the print statement inside the bool value checking if condition. Because we know only the prime numbers will pass that if condition. We have completely eliminated the last for loop that used to print true values of array. Hence making our code shorter. The backdrop is we now need to run the loop till n not root(n), like in previous simple implementation.

The C++ implementation of the optimized Sieve of Eratosthenes Algorithm has been provided below:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void Seive(int n){
    vector<bool> isPrime(n+1, true);//initializing all the elements in the boolean vector as true
    int i, j;
    for(i=2;i<=n;i++){
        if (isPrime[i]==true){//if the value is true then it is a prime number
            cout<<i<<" ";//since the current number is prime we can directly print it
            for(j=i*i;j<=n;j=j+i){//all the composite numbers before i*i are already marked as false 
                isPrime[j]=false;//marking all the multiple equal or greater than the square of i as false
            }
        }
    }
}
//The main function will be written as follows
int main(){
    int num = 20;
    cout<<"All the prime numbers till "<< num <<" are as follows:"<<endl;
    Seive(num);//calling the Seive function to implement the algorithm
    return 0;
}

Output
All the prime numbers till 20 are as follows:
2 3 5 7 11 13 17 19

The time complexity of Sieve of Eratosthenes algorithm is O(nloglogn) that is almost equal to O(n) as loglogn become very less on asymptotic values of n.