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:
- Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
- Initially, let p equal 2, the smallest prime number.
- 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).
- 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.
- 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
Top comments (2)
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
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?