Sieve of Eratosthenes

Why is this algorithm efficient?

One of the best algorithm to check if a number is prime or not is given below:

The time complexity of this algorithm is O(√n), here 'n' is the number under consideration. Suppose we have a total of 'Q' numbers , Q and n can be as large as a million. Now we have to check each number whether it is prime or not.

Since, n and Q are the order of 10^6, therefore in worst case, our machine would have to do O(Q√n) computations ie ~10^6*10^3=10^9 computations, which will take more than the expected time!

Here comes this Sieve algorithm. It is a preprocessing technique which generates all the prime numbers between 0 and a given limit. It is very efficient in cases we have to find all the prime numbers between a range.

Time Complexity O(nlog(n)log(n))
Auxiliary Space O(n)

Implementation of the algorithm using C++