Sieve of Eratosthenes

Sieve of Eratosthenes Algorithm is an algorithm to find all prime numbers between two numbers or all prime numbers less than or equal to a number, with the most efficient approach having time complexity O(n*log(log(n))) for a given number (n). This algorithm basically use a array or vector to store whether a number is prime or not. And deals with the indices to set a number as prime or composite.

How Sieve of Eratosthenes works:

1. First, we declare an array/vector of size n (here n is the number up to which we have to find prime numbers) and set all elements of the array to 1.
2. Then we iterate from i=2 to square root of n and for every iteration there is a nested loop which iterate through the i to square root of n, which sets every array index which is a multiple of the number to 0. This runs till the i become square root of n.
3. When this nested loop ends all the non-prime numbers having value 0 because we set the multiples as 0. So, automatically we found the prime number as those array index which having value 1.

Here’s an implementation for the above approach:

In C++:

#include<iostream>
#include<vector>
using namespace std;
void Print_prime(vector<int> arr,int n) // Declaration of a function to calculate prime numbers
{
   arr[0]=0;// as we know 0 can never be prime so set its value to 0
   arr[1]=0;// as we know 1 can never be prime so set its value to 0
   /*
   declaration of nested loop which sets the multiples
   of every i to 0 (as we know a prime number has no factors than 1 or itself)
   */
   for(int i=2;i*i<=n;i++)
   {
      if(arr[i]==1)
      {
       for(int j=i;j*i<=n;j++)
       {
           arr[i*j]=0; // setting all non-prime numbers to 0
       }
      }
   }
   cout<<"All Prime Numbers Till "<<n<<"\n";
   // printing all prime numbers (array elements that have value = 1)
   for(int i=0;i<n;i++)
   {
       if(arr[i]==1)
         cout<<i<<" ";
   }
}
int main()
{
  cout<<"Enter the number till You want to print all prime"<<"\n";
  int number;
  cin>>number;
  vector<int> arr(number,1); // declare a vector and set value 1 to every element of the vector
  Print_prime(arr,number); // calling function to print all prime till n
  return 0;
}

Input:

Enter the number till You want to print all prime
15

Output:

All Prime Numbers Till 15
2 3 5 7 11 13

A modified implementation for this algorithm is:

In C++:

#include<iostream>
#include<vector>
using namespace std;
void Print_prime(vector<int> arr,int beg,int n) // Declaration of a function to calculate prime numbers
{
   arr[0]=0;// as we know 0 can never be prime so set its value to 0
   arr[1]=0;// as we know 1 can never be prime so set its value to 0
   /*
   declaration of nested loop which sets the multiples
   of every i to 0 (as we know a prime number has no factors than 1 or itself)
   */
   for(int i=2;i*i<=n;i++)
   {
      if(arr[i]==1)
      {
       for(int j=i;j*i<=n;j++)
       {
           arr[i*j]=0; // setting all non-prime numbers to 0
       }
      }
   }
   cout<<"All Prime Numbers In this range "<<n<<"\n";
   // printing all prime numbers (array elements that have value = 1)
   for(int i=beg;i<=n;i++)
   {
       if(arr[i]==1)
         cout<<i<<" ";
   }
}
int main()
{
  cout<<"Enter the number range You want to print all prime"<<"\n";
  int number1,number2;
  cin>>number1>>number2;
  vector<int> arr(number2+1,1); // declare a vector and set value 1 to every element of the vector
  Print_prime(arr,number1,number2); // calling function to print all prime till n
  return 0;
}

Input:

Enter the number range You want to print all prime
2   25

Output:

All Prime Numbers In this range
2 3 5 7 11 13 17 19 23

This article is exclusively contributed by Amit Singh Bisht.

Read Next: Functions, Prototypes & Recursion in C++