Sieve of Eratosthenes, What is it?
Tags: algorithms, todayilearned, programming, javascript
Published: 2021-07-21 18:52:40

![Eratosthenes](https://www.famousmathematicians.net/photos/eratosthenes.jpg)
<figcaption>Image source : famousmathematicians.net</figcaption>

## 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
```javascript
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.
```javascript
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.
```javascript
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,
```javascript
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.

 ![Hurray](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2247gqevr4odteacp7gz.png)

## 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.
```javascript
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`.
```javascript
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`.
```javascript
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`.
```javascript
 for (let num = 2; num <= n; num++) {
   if (Boolarray[num] == true) {
     console.log(num);
   }
 }
```
So, we end with this final code,
{% gist https://gist.github.com/code-reaper08/436ec99ce3e01eedb2176a81de7c8304 %}

You can also use the JSFiddle, to change the hard-coded input `n` to your wish.

#### [JSFiddle link](https://jsfiddle.net/Vishwa_R/t20acbsj/)

### Attributions:
Cover-image : Photo by <a href="https://unsplash.com/@jaanam9?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Jaanam Haleem</a> on <a href="https://unsplash.com/s/photos/mesh?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>


### Thanks for reading ✨
Feel free to correct and give feedbacks. Like it?, then 💖 it.