Sieve of Eratosthenes

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 –

 

Download   Run Code

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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂