More
AlgorithmsSieve of Eratosthenes

# 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;// as we know 0 can never be prime so set its value to 0
arr=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;// as we know 0 can never be prime so set its value to 0
arr=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++ 1. Naveen

It’s great man .

2. Suryansh

Great 👍

3. Sumit

Well articulated

Subscribe Today

Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.