Sieve of Eratosthenes is a very efficient algorithm that can be used in most coding competitions involving prime numbers in the range of a given number n.

The algorithm starts off by assuming that all the numbers in the range 2 to n are prime. Now we traverse the list starting from 2 to √n.

We traverse only until √n because every non-prime number has a root lesser than or equal to √n. This is because a non-prime number can be expressed as

number = a * b

where a is lesser than or equal to √n and b is greater than or equal to √n.

For every number we encounter, we strike of all it’s multiples in the list. This process continues for all numbers which aren’t striked off. Hence, we get the final list of all prime numbers in range 2 to n.

Here is a C++ program implementing Sieve of Eratosthenes –

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 |
#include <iostream> #include <math.h> using namespace std; #define MAX 100 // Function to print prime numbers in the range of a given number n void SieveOfEratosthenes(int n) { int a[MAX]; for (int i = 0; i <= n; i++) // initialize all numbers as prime a[i] = 1; for (int i = 2; i <= sqrt(n); i++) { if (a[i] == 1) // checks if i is prime { for (int j = 2; i * j <= n; j++) a[i * j] = 0; // multiples of i are not prime } } for (int i = 2; i <= n; i++) if (a[i] == 1) cout << i << " "; // prints primes } // main function int main() { // print primes less than 100 SieveOfEratosthenes(100); } |

`Output: `

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Time complexity of this algorithm is O(n log(log(n))).

**Author: **Harish Anjaneya

**Happy reading!**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply