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.


  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


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)
		for(int j=i*i;j<=n;j+=(2*i) { 
			    p[j] = 0;
int main()
	int n;
	for(int i=0;i<=N;i++){
			cout<<i<<" ";