Sieve of Eratosthenes is an algorithm to find all prime numbers up to a given range. This concept is very important when it comes to competitive programming because it is the most efficient way to find all primes smaller than n until variable n is smaller than 10 million.

Example n = 7 2, 3, 5, 7 n = 15 2, 3, 5, 7, 11, 13

#### Let us understand how it works

Since a prime number have only two divisors 1 and itself. We will use this concept to find all the prime numbers up to a given range.

- Create a list of all consecutive integers from 2 to n(n is our range).
- Initially let p=2, the first prime number.
- Starting from 2p and mark all the factors of p in the range 2p to n. These factors will be
*2p, 3p, 4p, 5p*and so on - Find the next unmarked number greater than p and repeat step 2. If there is no such number stop.

#### Example

Let’s understand the working of Sieve of Eratosthenes for n = 50. Here we require to print all the prime numbers in the range 2 – 50.

List of all numbers from 2 to 50. Note 1 is neither prime nor not prime.

Let p=2, using step 2, we will mark all the factors of 2 in range 4*(2p)* to 50 i.e. 2*, 4, 8……5*0.

Now 3 is the next, not marked integer. So, now p=3, using step 2, we will mark all the factors of 3 from 6*(3*p)* till 50* i.e. 6, 9…….48*

Now 5 is the next, not marked integer. So, now p=5, using step 2, we will mark all the factors of 5 from 10*(2*p)* to 50* i.e. 10, 15 … 50 *

We will continue this process for all the unmarked integer and our final table will look as represented below.

So, the prime numbers in range 2 to 50 are unmarked one – 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

##### Implementation of the above algorithm in CPP

##### Output

Prime numbers between 2 to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

The time complexity of the above algorithm is **O(n*log(log n))**.