Sieve of Eratosthenes : The Most Efficient & Fast Way To Find The Prime Numbers

Sieve of Eratosthenes : The Most Efficient & Fast Way To Find The Prime Numbers

Sieve of Eratosthenes prime numbers linear time fast way thecsengineer

Intro :

So, as a programmer one of the first things that we learn is to check or  find the prime numbers. And the questions based on one algorithm comes up in different ways like : "Find the prime numbers between 2 to n integers" or "Find the nth prime number ". 

In this blog we are going to learn the algorithm which will never result in time limit exceeded as compared to a solution where we use the brute force or naieve algorithm .

This algorithm is known as Sieve of Eratosthenes .

Sieve Of Eratosthenes :

An algorithm which is used to find all the prime numbers in a given range .

Time Complexity : O(n log log n)

 The Idea :

        So, the idea of the algorithm is that a number is called a prime number only if no smaller prime numbers divide it .

Understanding the algorithm :

   Lets assume we are given a number a 5 and so what we do is first assume that all are prime numbers so we mark all of them 'true' in an array .Then we iterate through each one of it and and check if it is true then we mark all the numbers that is a multiple of the current number in the range starting from the number's square till the end of the given range .So, basically we are just marking out the numbers which are divisible by the smaller prime numbers and at last we are left with the numbers which got divided by no one so marked 'true' till the end . And of course we mark 1 and 0 as 'false' in the beginning as they are not prime and if considered would divide every other number in front of them and thus making them 'false' .

The Code :

From the Classical Algorithm Reposititory. Do give a star ! ๐ŸŒŸ

Implementation :

✔️First we make an array of size of the given range and initialize all  its value as 'true' assuming that all the numbers  are prime numbers.               

✔️Mark 0 and 1 as 'false' .

✔️Iterate through each of the number from 2 to n(last digit of the range).

✔️Check if the current number in the loop is marked 'true' not and whether it's square is less than n or the range as we have to traverse from the square of the current number to n marking 'false' all the multiples of the  current number .

✔️If it the check is passed we traverse from the square of the current  number till n and mark all of it's multiples 'false'.                            

So, at the end we are left with all those numbers which were not divisible by anyone marked 'true' or as we called those numbers as Prime Numbers in Earth. 

Thanks, Keep Learning ๐Ÿงก