Sieve of Eratosthenes, What is it?

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.

How it works?

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.

Execution in JS 💻

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 kand 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.

Now it's all logging it onto the console 🎉

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,

	let Boolarray = [];
	let n = 100;
	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;
	}
	}
	}

	console.log(Boolarray)
	for (let num = 2; num <= n; num++) {
	if (Boolarray[num] == true) {
	console.log(num);
	}
	}