45
Sieve of Eratosthenes, What is it?
Sieve of Eratosthenes is an algorithm devised by the Eratosthenes of Cyrene. It does the job of finding all the prime numbers within a given upper limit. This ancient algorithm is efficient and smart till the upper limit is a few billions. So we'll discuss the process and JavaScript code for the same, below.
The algorithm starts with generating a list of all numbers starting from 2 to n (where n is the upper limit), with the assumption of all the numbers in the list are prime. It starts from 2 and removes all the multiples of 2 in the list by traversing the list in the interval of 2.
So, now we consider n as 10
let sample_array = [2, 3, 4, 5, 6, 7, 8, 9, 10];
Starting from 2, it removes the multiples of 2 by traversing the above list in a step count of 2.
Note: '*' below means removed from list.
let sample_array = [2, 3, 4*, 5, 6*, 7, 8*, 9, 10*];
After removing all the multiples of 2, we move to the next non-removed number (that is 3), now from 3, we traverse the list with the step count of 3 and remove its multiples.
let sample_array = [2, 3, 4*, 5, 6*, 7, 8*, 9*, 10*];
We then proceed to the next non-removed number, which is 5. But here's the thing, the multiples of 5 are already removed from the list. We just make sure when to end this cycle of traversal and removal by calculating the square of 5, that is 5*5 = 25, which is obviously greater than n that is 10. So we stop the process and get the remaining elements, which are prime.
Here's the final list we get,
let sample_array = [2, 3, 5, 7];
Hurray!, we've done with the theory part, let's get our hands dirty with some JS to actually code it.
Let's start by creating an empty array called Boolarray
, why naming 'Bool', because we are going for a Boolean array. We also initialize the value of n as 20.
let Boolarray = [];
let n = 20;
Remember, we first made an assumption that all the numbers in the list (here array) are prime. So we use true
for is prime
and false
for not a prime
, with this in mind we first fill the empty array with boolean values of all True
(based on our assumption). We use a for
loop with iterator i
to iterate from 1 to n and fill the array with True
.
let Boolarray = [];
let n = 20;
for (var i = 0; i < n; i++) {
Boolarray.push(true);
}
Now, we have an array of length 20 with true
on all indexes. We now follow the procedure of Sieve of Eratosthenes by starting the for
with iterator j
from 2 to j*j<=n (j*j<=n checks when to end the looping). If the current element in the array is true
, we then loop over its multiples with iterator k
and a step count, (according to the current element) and mark them false
.
let Boolarray = [];
let n = 20;
for (var i = 0; i < n; i++) {
Boolarray.push(true);
}
for (let j = 2; j * j <= n; j++) {
if (Boolarray[j] == true) {
for (let k = 2 * j; k <= n; k += j) {
Boolarray[k] = false;
}
}
}
After this execution, we are left with a Boolean array, which contains true
in places of prime (remember true
β is prime) and false
in places of non-prime numbers in the array.
We use another for
loop to iterate on Boolarray
with iterator num
, starting from 2 to num<=n. We console log only the num
's which contains true
in the Boolarray
.
for (let num = 2; num <= n; num++) {
if (Boolarray[num] == true) {
console.log(num);
}
}
So, we end with this final code,
You can also use the JSFiddle, to change the hard-coded input n
to your wish.
Cover-image : Photo by Jaanam Haleem on Unsplash
Feel free to correct and give feedbacks. Like it?, then π it.
45