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


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

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


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

Notify of