Best way to get all prime numbers (Sieve of Eratosthenes)

Introduction

In almost every interviews, an optimized way of searching is a very common thing nowadays, especially when it comes to numbers it becomes more interesting. Today we will be discussing one of the most popular questions among the interviewers, finding all the prime numbers from a series of 0 to 1 million numbers. Looping through from 0 to 1 million number will definitely give you the desired outcome however in terms of performance and time complexity it will not perform good, so the catch is if this is not the ideal way of doing this then what will be the other option.

From the title, most of you have already guessed its something called "Sieve of Eratosthenes" well this is an ancient algorithm to eliminate all the prime numbers from a long series. Let's find out what does this algorithm says

Sieve of Eratosthenes

Wikipedia says "In mathematics, the Sieve of Eratosthenes is a simple and ingenious ancient algorithm for finding all prime numbers up to any given limit."

How does it do

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with a constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

Algorithm & Implementation

The algorithm says the following

A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the smallest prime number.
3. Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

See how cleverly it manage to find all the prime numbers in an efficient way. Now let's look at the implementation of the algorithm. We will be doing it by using javascript.

function GenerateSieve(max)
{
    // Creating an array indicating whether numbers are prime.
    const is_prime = new Array(max+1);

    for(let i=2; i<=max; i++)
    {
        is_prime[i]=true;
    }

    //Crossing out multiplies
    for(let i=2; i<=max; i++)
    {
        //Check if its prime
        if(is_prime[i])
        {
            //Eliminate the multiplies of i
            for(let j=i*2; j<=max; j+=i){
                is_prime[j]=false;
            }
        }
    }
    return is_prime;
}

Lets understand the code line by line

    // Creating an array indicating whether numbers are prime.
    const is_prime = new Array(max+1);

In the above snippet, you can see we are creating an array

   for(let i=2; i<=max; i++)
    {
        is_prime[i]=true;
    }

Through this loop, we are marking all the numbers in the array as a prime number, except 0,1 and 2 as we know already know about their prime and non-prime stands

0,1 being non-prime numbers and 2 being the smallest prime number, we have initialized the loop from 2 and mark all the numbers beyond that as prime numbers. So as of now, all the elements are prime numbers in the is_prime array.

    for(let i=2; i<=max; i++)
    {
        //Check if its prime
        if(is_prime[i])
        {
            //Eliminate the multiplies of i
            for(let j=i*2; j<=max; j+=i){
                is_prime[j]=false;
            }
        }
    }

Here in the first loop, we are iterating through each element starting from 2 and then in the second loop we are eliminating the composite numbers from the _is_prime array, so in forward we are already removing the composite numbers from the array so as a result the outer loop may run for nth number and inner loop will not run for that time as the following statement will stop it running

   if(is_prime[i])
   {
        ....
   }

Hope, the algorithm and its implementation now clear. The complete implementation of this algorithm can be found in both javascript and in c#

So if you've liked this article then please like it, this will give me confidence to write more article in future. Also if you want to get daily updates or resolve any of your doubts on your #100daysofcode program then feel free to DM me on twitter. My twitter handle is @avishekp86