DEV Community

loading...
Cover image for Best way to get all prime numbers (Sieve of  Eratosthenes)

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

Avishek Patra
Check my twitter profile for bio, if like then follow me
・4 min read

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;
}
Enter fullscreen mode Exit fullscreen mode

Lets understand the code line by line

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

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

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

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;
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

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])
   {
        ....
   }
Enter fullscreen mode Exit fullscreen mode

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

Discussion (2)

Collapse
lurb3 profile image
lurb3

Honest question, what is the purpose of these interview questions?
To test if you can come up with an ancient solution that probably took some time to figure out.

Or to test if you can memorize an algorithm that you've seen on the internet that you know it's typical interview question and vomit it during the interview?

I am sorry but I don't get why people make "puzzle" questions like fizzbuzz and whatever, oh and they don't let you use internet... Because when you code you never use internet

Well anyway, thanks for your explanation

Collapse
lurb3 profile image
lurb3

By the way,

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

Won't this crash if you test with 1 million number?