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 Eratosthenes is a simple, ancient algorithm for finding all prime numbers up 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

1. First we Mark all the numbers as a prime number.
2. 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.
3. 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.

1. 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;
}