# .css-df1pn7{display:block;width:16rem;}     # Sieve of Eratosthenes: An Interesting Algorithm

Divine Orji
·Aug 13, 2022·

Subscribe to my newsletter and never miss my upcoming articles

• A little back story 📜
• What is this sieve you speak of? 🤔
• Interesting! How does it work? 🧐
• Nice! Are there any limitations to be aware of? 👀
• A few parting words 🤗
• Further reading 📚

## A little back story 📜

One day, while learning algorithms in JavaScript, I found this challenge:

Using a for loop, iterate from 0 to 100 and return an array of all prime numbers within that range.

It seemed easy initially, but I couldn't quite figure it out. So I did a google search and discovered an algorithm that does it perfectly - the Sieve of Eratosthenes.

## What is this sieve you speak of? 🤔

The Sieve of Eratosthenes is an ancient math algorithm created by Eratosthenes of Cyrene. It finds all prime numbers between 0 and a given limit.

## Interesting! How does it work? 🧐

Let's break it down:

• Our input is a positive number representing the limit.
• The algorithm loops through all numbers between 0 and our input.
• In each iteration, if the number is a prime, it marks all multiples of that number as non-primes.

Cool right?! Now let's solve our original challenge:

``````function getPrimes(input) {
// Create an array where each element starts as true
const numsArr = Array.from({ length: input + 1 }, () => true);

// Create an array to store the prime numbers
const primeNumbers = [];

/*
Loop through numsArr starting from numsArr
because 0 and 1 are definitely not prime numbers
*/
for (let i = 2; i <= input; i++) {
// Check if numsArr[i] === true
if (numsArr[i]) {
// add the i to the primeNumbers array

/*
convert all elements in the numsArr
whose indexes are multiples of i
to false
*/
for (let j = i + i; j <= input; j += i) {
numsArr[j] = false;
}
}
}

}

console.log(getPrimes(100));
``````

In the code above, we did the following:

• Created an array of `true` elements. JavaScript arrays are zero-indexed, so we set `length: input + 1` to take advantage of that.
• Created `primeNumbers[]` to store the prime numbers.
• Used a `for` loop to iterate over each element in `numsArr[]`. If the current element is `true`, add it to `primeNumbers[]` and convert all elements in multiples of its index to `false`.
• Returned `primeNumbers[]`, which now contains all the prime numbers with 0 and our input.

So this works, but there’s a slight problem (or a major one, depending on the input size). At some point during the loop, all possible non-primes in the array are already `false`, but reaching a `true` element still triggers its nested loop. That’s redundant! 🙄

Let’s optimize! 🚀

``````// Sieve of Eratosthenes Algorithm

function getPrimes(input) {
// Create an array where each element starts as true
const numsArr = Array.from({ length: input + 1 }, () => true);

// Loop through numsArr starting from numsArr
// keep running the loop until i is greater than the input's square root
for (let i = 2; i <= Math.floor(Math.sqrt(input)); i++) {
// Check if numsArr[i] === true
if (numsArr[i]) {
/*
convert all elements in the numsArr
whose indexes are multiples of i
to false
*/
for (let j = i + i; j <= input; j += i) {
numsArr[j] = false;
}
}
}

/*
Using Array.prototype.reduce() method:
loop through each element in numsArr[]
if element === true,
add the index of that element to result[]
return result
*/
const primeNumbers = numsArr.reduce(
(result, element, index) =>
element ? (result.push(index), result) : result,
[]
);

}

console.log(getPrimes(100));
``````

What’s happening in the code above? 😵‍💫

Mathematically, it is impossible to get any new multiples past the square root of any given input. To put it simply, by the time we get to the square root of `input`, all possible multiples in `numsArr[]` would already be converted to `false`, so there’s no need to keep checking for multiples.

So here’s what we did:

• Updated the `for` loop to end when `i <= Math.floor(Math.sqrt(input))` is false.
• Used JavaScript’s `reduce()` method to loop through `numsArr[]` and return an array containing the `index` of all `true` elements.

Fun fact: This optimization will also work if we replace the first `for` loop with:

``````// keep running the loop until input is less than i^2 (i squared)
for (let i = 2; i * i <= input; i++) {
// same super-awesome code hehehe!
}
``````

Try it! 😉

## Nice! Are there any limitations to be aware of? 👀

The Sieve of Eratosthenes works efficiently with small inputs - `n < 10 million` (😒 is 10 million small???). However, larger inputs take a lot of time and memory. The segmented sieve is a proposed solution to this issue.

## A few parting words 🤗

There are different versions of this algorithm, each tackling some of the limitations of the original. Learning this algorithm broadened my knowledge of nested loops, prime numbers, and time complexity. To explore these topics in-depth, Check out the resources below.