Today, I'll be talking about an interesting and famous algorithm **"The Sieve of Eratosthenes"**. Let me give an overview about the use of this algorithm.

According to wikipedia,

The

Sieve of Eratosthenesis a simple, ancient algorithm for finding allprime numbersup to any given limit.

### What is a Prime Number?

A number which is divisible only by \(1\) and itself.

### So, How to check if a number is Prime or not?

The general approach/method for checking if a number is prime or not is by iterating through all the numbers from \(2\) to \((n-1)\), and if we encounter any such number which divides the number \(n\) we say that the number \(n\) is **not a prime number.** If we talk about the **Time Complexity** of this approach then it is going to be \(O(N)\), as in the worst case we will be iterating till the last number \(N\). Though this approach can be optimised a little bit by checking for the prime numbers till \(n/2\), or furthermore it can be optimised only by iterating till \(\sqrt{n}\).

**Now suppose you are asked to generate all the prime numbers till a given number \(n\)**

With this apporach, Your code time complexity will come out to be \(O(N\sqrt{N})\). Which is approaximately \(O(N^2)\). Hence it's not a good approach, so this is where **The Sieve of Eratosthenes** comes into the picture.
With which you can find out the all the prime numbers till \(1000000\) in \(O(Log(Log(N)))\) time. So, here's the **algorithm** for finding the prime numbers till 1 million using **prime sieve**.

### Algorithm

- First we Mark all the numbers as a prime number.
- We mark \(0,1,2\) as prime initially and we do not consider marking the multiples of \(2\) as prime as they're even numbers.
- Then, starting from \(3\) we mark all of it's multiple as false (not prime), followed by \(5\) and so on.

Note: Here we're considering only odd numbers, as even numbers are not prime.

- This way we are left only with the prime numbers till \(n\).

Here's the code you can refer

```
#include<iostream>
using namespace std;
int p[N+1] = {0};
void GenerateSieve(int n)
{
p[0] = p[1] = 0;
p[2] = 1;
for(int i=3;i<=n;i+=2){
p[i] = 1;
}
for(int i=3;i<=n;i+=2)
{
if(p[i]){
for(int j=i*i;j<=n;j+=(2*i) {
p[j] = 0;
}
}
}
}
int main()
{
int n;
cin>>n;
GenerateSieve(n);
for(int i=0;i<=N;i++){
if(p[i]){
cout<<i<<" ";
}
}
cout<<endl;
}
```