Introduction
Sieve of Eratosthenes is used to print all of the prime numbers in a given range efficiently. It is widely used in the world of competitive programming, where we try to find solutions in a betteroptimized way.
Sieve of Eratosthenes is an ancient algorithm of 200+ years old, which is a simple and elegant method to find primes that are less than or equal to ‘N’ where ‘N’ is the upper range to be taken as input.
Note:
 A prime number has two factors: 1 and the number itself.
 0 and 1 are not prime numbers.
Read more about segmented sieve and try out problems here.
Finding all the prime numbers using sieve
Let us assume that we have numbers from 1 to 50.
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
Since 1 is neither composite nor prime, we will exclude 1 from the table where we have to find all the prime between the range [1, 50].
Now, we will mark all the multiples of 2 as below.
2^{2} = 4. Hence, we will mark from 4 onwards.
2 
3 
4 
5 
6 
7 
8 
9 
10 

11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
Now, we will move forward to mark all the multiples of 3.
3^{2} = 9. Hence, we will mark from 9 onwards.
2 
3 
4 
5 
6 
7 
8 
9 
10 

11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
Now, we will move forward, and here we notice that ‘4’ is marked. Hence, we move again to the next number to mark all the multiples of 5.
5^{2} = 25. Hence, we will mark from 25 onwards.
2 
3 
4 
5 
6 
7 
8 
9 
10 

11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
Now, we will move forward, and here we notice that ‘6’ is marked. Hence, we move again to the next number to mark all the multiples of 7.
7^{2} = 49. Hence, we will mark from 49 onwards.
2 
3 
4 
5 
6 
7 
8 
9 
10 

11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
Now moving on to the next number, ‘8’ is marked and its square is 64, which is more than our given range, we will stop working in the loop here. By doing this whole process, we eliminated all the nonprime numbers to get only the prime numbers.
The prime no.s are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 