I recently solved a coding challenge that required me to find all prime numbers up to a given number. I came up with a brute force solution first to get things working and get the brain juices flowing. Then I made some tweaks to make some improvements on the time complexity. Finally, I did some research to find an even better solution. I found the Sieve of Eratosthenes algorithm, which is an ancient algorithm for finding prime numbers. In this post, we'll go over how it works and how to implement it in JavaScript.

## Brute force solution

The first thing I did was come up with a brute force solution. I started by iterating over all numbers from 2 to the given number and checking if each number was divisible by any number less than it. If it was, then it was not a prime number and I skipped it. If it wasn't divisible by any number less than it, then it was a prime number and I added it to the final array.

This one isn't very efficient due to the nested loops (having a time complexity of `O(n^2)`

), but it's a good starting point to understand the problem.

1function bruteForceGetPrimes(n) {2 const primes = [];34 for (let i = 2; i <= n; i++) {5 let isPrime = true;67 for (let j = 2; j < i; j++) {8 if (i % j === 0) {9 isPrime = false;10 break;11 }12 }1314 if (isPrime) {15 primes.push(i);16 }17 }1819 return primes;20}

## First optimization

After getting the brute force solution working, I started thinking about how I could make it more efficient. I realized that I didn't need to check if a number was divisible by every number less than it. I only needed to check if it was divisible by prime numbers less than it. For example, I don't need to check if a number is divisible by 4 if I've already checked if it's divisible by 2 (since 4 is divisible by 2). So I created an array of prime numbers and checked if each number from 2 to `upperBound`

was divisible by any of those prime numbers. If it was, then it was not a prime number and I excluded it from the array. If it wasn't divisible by any of those prime numbers, then it was a prime number and I added it to the array. Then I filtered the array of prime numbers to only include numbers greater than or equal to `lowerBound`

.

This one is a little better because the nested loop (`primes.some`

) iterates over fewer numbers and even exits the loop early as soon as it finds a prime that divides evenly into the current number. So not quite `O(n)`

, but better than `O(n^2)`

.

1function firstOptimizationGetPrimes({upperBound, lowerBound = 0}) {2 if (upperBound < lowerBound || upperBound < 2) {3 return [];4 }56 const primes = [];78 for (let i = 2; i < upperBound; i++) {9 if (i === 2) {10 primes.push(i);11 } else {12 const isNotPrime = primes.some(prime => i % prime === 0)1314 if (!isNotPrime) {15 primes.push(i);16 }17 }18 }1920 return primes.filter(prime => prime >= lowerBound);21};

## The Sieve of Eratosthenes Algorithm

After coming up with my own brute force solution and iterating on it to make some optimizations, I did some research to see if there was an even better way to do it. I found the Sieve of Eratosthenes algorithm, which is an ancient algorithm for finding prime numbers. It's a very simple algorithm, but it's also pretty efficient.

Essentially, the algorithm works by starting with a list of all numbers from 2 to the given number (because 0 and 1 are not prime). Then, starting with 2, it removes all multiples of 2 from the list. Then it moves on to 3, and removes all multiples of 3 from the list. It skips 4 because 4 has already been removed as a multiple of 2. So it goes on to 5 and continues this process until it reaches the given number. The numbers that are left in the list are all prime numbers.

So rather than checking the divisibility of each number in the given range by each number less than it, we can just remove all multiples of each prime number in the given range. This is more efficient because we only have to check divisibility by prime numbers, which are fewer in number than all numbers less than the given number.

### JavaScript Implementation

Using JavaScript (because I'm a frontend gal), an implementation of this algorithm might look something like this:

1function regularSieveGetPrimes(n) {2 // Create a boolean array of length n + 1 and initialize all entries as `true`3 // (where each index represents a number)4 // We start by assuming all numbers are prime5 // If a number is proven to NOT be prime, we set its value to `false`6 const primeBools = Array.from({ length: n + 1 }, (_, i) => true);78 // start at 2 since we know 0 and 1 are not prime9 for (let potentialPrime = 2; potentialPrime * potentialPrime <= n; potentialPrime++) {10 // If `prime[potentialPrime]` is truthy, then it is a prime11 if (primeBools[potentialPrime]) {12 // Update all multiples of `potentialPrime` to be `false` (aka not prime)13 for (let primeMultiple = potentialPrime * potentialPrime; primeMultiple <= n; primeMultiple += potentialPrime) {14 primeBools[primeMultiple] = false;15 }16 }17 }1819 // extract the primes from our boolean array20 const primes = [];2122 // start at 2 since we know 0 and 1 are not prime23 for (let i = 2; i <= n; i++) {24 if (primeBools[i] === true) {25 primes.push(i);26 }27 }2829 return primes;30}

#### Boolean array

The first thing we do is create an array to keep track of the "primeness" of our numbers. We initialize this array to be the length of the given number plus one. Each index in this array represents a number from 0 to the given number. So we add 1 to the length because we want to include the given number in our array since array indices start at 0. And finally, all values in this array are initialized to `true`

because we assume that all numbers are prime until proven otherwise.

Fun fact: a non-prime number is called a composite number.

const primeBools = Array.from({ length: n + 1 }, (_, i) => true);

#### Loop through potential primes

Now that we have our array of booleans, we can start checking the numbers. Remember, with this algorithm we are "flagging" which numbers composite, or not prime, by determing which numbers are multiples of primes. We can do this by using nested loops.

##### Outer loop

For the outer loop, we want to check every number between 2 and the given number, incrementing by 1. We start at 2 because 2 is the first prime number. And instead of iterating all the way up to the given number, we just need to go up enough to reach the *square root* of the given number. *This is because the square root of the given number is the largest possible prime factor of the given number* (remember, a prime factor is a prime number that can perfectly divide the given number). So we don't need to check any numbers larger than the square root of the given number because everything larger that is not prime will have already been flagged by a smaller prime number.

For example, if the given number `n`

is 49 (whose square root is 7), we only need to check up to 7 because 7 is the largest possible prime factor of 49. We don't need to worry about larger prime numbers (like 11, 13, 17, etc.) because they can't be prime factors of 49. And with this algorithm, we're only concerned with flagging which numbers are NOT prime. So any non-prime number larger than the square root of the given number will have already been flagged as not prime by a smaller prime number. In our example here, 8 will have been flagged by 2, 9 by 3, 10 by 2, 12 by 2, 14 by 2, 15 by 3, etc. So we don't need to keep checking past 7.

Going back to our code, if our current number, `potentialPrime`

, is prime (or `true`

in our `primeBools`

array), we loop through all of its multiples in our inner loop and set them to `false`

in our boolean array (we'll do this in a second). For example, if `potentialPrime`

is 5, we can mark all multiples of 5 (10, 15, 20, etc.) as not prime.

1for (let potentialPrime = 2; potentialPrime * potentialPrime <= n; potentialPrime++) {2 // If `prime[potentialPrime]` is truthy, then it is a prime3 if (primeBools[potentialPrime]) {4 // we'll do our inner loop here5 }6}

##### Inner loop

For our inner loop, we start at the square of `potentialPrime`

because all of the multiples of `potentialPrime`

that are *less* than its square have already been marked as `false`

in our boolean array. For example, if `potentialPrime`

is 3, we start our inner loop at 9 (the square of 3) because 6, while being a multiple of 3, has already been marked as `false`

in our boolean array when `potentialPrime`

was at 2 (since 6 is also a multiple of 2).

1// Update all multiples of `potentialPrime` to be `false` (aka not prime)2for (let primeMultiple = potentialPrime * potentialPrime; primeMultiple <= n; primeMultiple += potentialPrime) {3 primeBools[primeMultiple] = false;4}

#### Return the primes

Finally, we loop through our boolean array and push the index of all of the `true`

values to a new array (since all `false`

values are composite/not prime). This new array will contain all of the prime numbers up to the given number.

1const primes = [];23// start at 2 since we know 0 and 1 are not prime4for (i = 2; i <= n; i++) {5 if (primeBools[i] == true) {6 primes.push(i);7 }8}910return primes;

#### Put it all together

So putting it all back together, our function looks like this:

1function regularSieveGetPrimes(n) {2 // Create a boolean array of length n + 1 and initialize all entries as `true`3 // (where each index represents a number)4 // We start by assuming all numbers are prime5 // If a number is proven to NOT be prime, we set its value to `false`6 const primeBools = Array.from({ length: n + 1 }, (_, i) => true);78 // start at 2 since we know 0 and 1 are not prime9 for (let potentialPrime = 2; potentialPrime * potentialPrime <= n; potentialPrime++) {10 // If `prime[potentialPrime]` is truthy, then it is a prime11 if (primeBools[potentialPrime]) {12 // Update all multiples of `potentialPrime` to be `false` (aka not prime)13 for (let primeMultiple = potentialPrime * potentialPrime; primeMultiple <= n; primeMultiple += potentialPrime) {14 primeBools[primeMultiple] = false;15 }16 }17 }1819 // extract the primes from our boolean array20 const primes = [];2122 // start at 2 since we know 0 and 1 are not prime23 for (let i = 2; i <= n; i++) {24 if (primeBools[i] === true) {25 primes.push(i);26 }27 }2829 return primes;30}

### Time and space complexity

The time complexity of this algorithm is `O(n log log n)`

, despite having nested loops. Let's break down the complexity of each part of the algorithm:

- The outer loop runs for each number from 2 to the square root of
`n`

. So the number of iterations for the outer loop is approximately`sqrt(n)`

. - The inner loop marks multiples of the current prime number as not prime. So the number of iterations for the inner loop is roughly
`n`

divided by the current prime number.

Based on that, you would think that the time complexity would be `O(n * sqrt(n))`

. However, the inner loop's iterations *decrease* as the algorithm progresses. So the overall number of operations is actually less than `n * sqrt(n)`

since there is a decreasing number of iterations in the inner loop as the algorithm flags multiples of primes. As primes are found and multiples are flagged, the inner loop's iterations decrease, in a way explained by the mathematical concept of harmonic series, resulting in the time complexity of `O(n log log n)`

.

The space complexity is `O(n)`

, because we create an array of booleans that is the length of the given number. The amount of space needed is directly proportional to the size of the given number.

We won't get any more in-depth about the time and space complexity of this algorithm or Harmonic Series in this post, but if you're interested in learning more, check out the Wikipedia article on the Sieve of Eratosthenes.

### Optimizations

While being pretty efficient in terms of time complexity, we can make it more efficient in terms of space complexity. If we are trying to find all of the prime numbers in a massive range, we don't want to have to worry about memory issues from creating an array that is the entire length of that range.

## Segmented Sieve

One solution to this is to use a segmented sieve. This is a variation of the Sieve of Eratosthenes that uses a smaller array to find the primes up to the square root of the given number. Then it uses this array to find the primes in the given range.

### JavaScript Implementation

Here's what a JavaScript implementation might look like, with some slight modifications to allow specifying a range of numbers rather than just a single number:

// `getSmallPrimes` is an implementation of the Sieve of Eratosthenes algorithm, but using the square root of the upper bound as our limitfunction getSmallPrimes(upperBound) {const primesArr = [];const limit = Math.sqrt(upperBound);const primesBoolArr = Array(Math.floor(limit) + 1).fill(true);// start at 2 since we know 0 and 1 are not primefor (let i = 2; i <= limit; i++) {if (primesBoolArr[i]) {for (let j = i * i; j <= limit; j += i) {primesBoolArr[j] = false;}}}// start at 2 since we know 0 and 1 are not primefor (let k = 2; k <= limit; k++) {if (primesBoolArr[k]) {primesArr.push(k);}}return primesArr;}// Segmented sieve implementationfunction segmentedSieveGetPrimes({upperBound, lowerBound = 0}) {// `smallPrimes` has primes in range [2, sqrt(upperBound)]const smallPrimes = getSmallPrimes(upperBound);// Initializes an array `primesInRange` of boolean values,// representing whether each number in the range [lowerBound, upperBound] is prime.// Initially, all numbers are assumed to be prime.const primesInRange = Array(upperBound - lowerBound + 1).fill(true);for (let prime of smallPrimes) {// the first multiple of `prime` which is in range [lowerBound, upperBound]// for example: 3's first multiple in range [28,40] is 30let lowerMultiple = Math.floor(lowerBound / prime);// If `lowerMultiple` is less than or equal to 1,// set it to the first multiple of `prime` greater than or equal to `lowerBound`// If `lowerMultiple` is less than or equal to 1,// it means the largest multiple found is less than `lowerBound`.// In this case, we adjust it to the first multiple of `prime` that// is greater than or equal to `lowerBound`.if (lowerMultiple <= 1) {lowerMultiple = prime + prime;}// If `lowerBound` is not divisible by `prime`,// adjust `lowerMultiple` to the next multiple of `prime` after `lowerBound`else if ((lowerBound % prime) !== 0) {lowerMultiple = (lowerMultiple * prime) + prime;}// If `lowerBound` is divisible by `prime`, keep `lowerMultiple` as the first multiple of `prime` in the range `[lowerBound, upperBound]` (which in this case is the value of `lowerBound`)else {lowerMultiple = lowerMultiple * prime;}// marks multiples of `prime` as not prime in the range [low, high]// by setting corresponding values in the `primesInRange` array to `false`for (let j = lowerMultiple; j <= upperBound; j = j + prime) {primesInRange[j - lowerBound] = false;}}const finalPrimesInRange = [];for (let i = lowerBound > 1 ? lowerBound : 2; i <= upperBound; i++) {if (primesInRange[i - lowerBound]) {finalPrimesInRange.push(i);}}return finalPrimesInRange;}

`getSmallPrimes`

function

The `getSmallPrimes`

function is just an implementation of the Sieve of Eratosthenes algorithm that we built previously, returning an array of all prime numbers from 2 to the square root of the given upper bound number.

1// `getSmallPrimes` is an implementation of the Sieve of Eratosthenes algorithm, but using the square root of the upper bound as our limit2function getSmallPrimes(upperBound) {3 const primesArr = [];4 const limit = Math.sqrt(upperBound);5 const primesBoolArr = Array(Math.floor(limit) + 1).fill(true);67 // start at 2 since we know 0 and 1 are not prime8 for (let i = 2; i <= limit; i++) {9 if (primesBoolArr[i]) {10 for (let j = i * i; j <= limit; j += i) {11 primesBoolArr[j] = false;12 }13 }14 }1516 // start at 2 since we know 0 and 1 are not prime17 for (let k = 2; k <= limit; k++) {18 if (primesBoolArr[k]) {19 primesArr.push(k);20 }21 }2223 return primesArr;24}

*We are using the square root of the upper bound as our limit instead of the upper bound itself (and adjusting the length of primesBoolArr accordingly)*. Remember, the reason we only need to find the primes up to the square root of the given number is because the multiples of all primes below the given number will be accounted for by the time we reach the square root of the given number. You can review the explanation of this logic in the outer loop section.

#### Setting up the inner loop

`getSmallPrimes`

gets us all of the primes in the range `[2, sqrt(upperBound)]`

. However, we want to find all of the primes in the range `[lowerBound, upperBound]`

. In order to do that, we want to loop through each prime number that we found in the `getSmallPrimes`

function. For each prime number, `prime`

, we want to find all of the multiples of `prime`

that are in the range `[lowerBound, upperBound]`

, starting with the smallest multiple of `prime`

that is in that range (highlighted on lines 15-17 in the code block below).

For example, if we are trying to find all of the primes in the range `[28, 40]`

, and we are starting with the first prime number in our `getSmallPrimes`

array (which is 2), we want to flag all of multiples of 2 that are in the range `[28, 40]`

. The first multiple of 2 that is in that range is 28. So we want to start our loop at 28 when `prime`

is 2. Then when `prime`

is 3, we want to start our loop at 30, and so on.

1function segmentedSieveGetPrimes({upperBound, lowerBound = 0}) {2 const smallPrimes = getSmallPrimes(upperBound);3 const primesInRange = Array(upperBound - lowerBound + 1).fill(true);45 for (let prime of smallPrimes) {6 let lowerMultiple = Math.floor(lowerBound / prime);7 if (lowerMultiple <= 1) {8 lowerMultiple = prime + prime;9 } else if ((lowerBound % prime) !== 0) {10 lowerMultiple = (lowerMultiple * prime) + prime;11 } else {12 lowerMultiple = lowerMultiple * prime;13 }1415 for (let j = lowerMultiple; j <= upperBound; j = j + prime) {16 primesInRange[j - lowerBound] = false;17 }18 }1920 const finalPrimesInRange = [];21 for (let i = lowerBound > 1 ? lowerBound : 2; i <= upperBound; i++) {22 if (primesInRange[i - lowerBound]) {23 finalPrimesInRange.push(i);24 }25 }26 return finalPrimesInRange;27}

Taking a look at the code, we initialize a `lowerMultiple`

variable. We want the value of this variable to be the first multiple of `prime`

that is in the range `[lowerBound, upperBound]`

.

If `lowerBound`

is a multiple of `prime`

, then `lowerMultiple`

will be a nice integer. However, in the case that it is not, we are rounding down to the nearest integer.

let lowerMultiple = Math.floor(lowerBound / prime);

What if `lowerMultiple`

is less than or equal to 1? This means that the `lowerMultiple`

we have just calculated, while still being a multiple of `prime`

, is actually below our `lowerBound`

. Not what we want. So in this case, we want to adjust `lowerMultiple`

to the first multiple of `prime`

that is greater than or equal to `lowerBound`

. We can do this by adding `prime`

to the initially calculated `lowerMultiple`

.

For example, if `lowerBound`

is 2 and `prime`

is 2, then `lowerMultiple`

will be 1. In this case, `lowerMultiple`

falls below our `lowerBound`

, so we want to adjust it to the first multiple of `prime`

that is greater than or equal to `lowerBound`

. In this case, that would be 4.

if (lowerMultiple <= 1) {lowerMultiple = prime + prime;}

If `lowerMultiple`

is greater than 1 and `lowerBound`

is NOT divisible by `prime`

, then we want to adjust `lowerMultiple`

to be the next multiple of `prime`

after `lowerBound`

. We can do this by multiplying `lowerMultiple`

by `prime`

and then adding `prime`

.

For example, if `lowerBound`

is 10 and `prime`

is 3, `lowerBound`

is NOT divisible by `prime`

. `lowerMultiple`

will come out to 3 (because we round down 10 divided by 3). So we want to adjust `lowerMultiple`

to be the next multiple of `prime`

after `lowerBound`

(in this case, that would be 12). So `lowerMultiple = (lowerMultiple * prime) + prime`

(or in this example, `lowerMultiple = 3 * 3 + 3`

)

else if ((lowerBound % prime) !== 0) {lowerMultiple = (lowerMultiple * prime) + prime;}

Otherwise, if `lowerBound`

IS divisible by `prime`

, then we want to keep `lowerMultiple`

as the first multiple of `prime`

in the range `[lowerBound, upperBound]`

(which comes out to be the value of `lowerBound`

, so you could just set it to `lowerBound`

or just do `lowerMultiple * prime`

).

else {lowerMultiple = lowerMultiple * prime;}

In summary, we're grabbing the first multiple of `prime`

that is in the range `[lowerBound, upperBound]`

and setting it to `lowerMultiple`

.

#### Getting all of the primes in a range

Now that we have our starting point for the inner loop with `lowerMultiple`

, we can loop through all of the multiples of `prime`

that are in the range `[lowerBound, upperBound]`

and flag them as not prime in the `primesInRange`

array.

We want to update the value at index `[potentialPrime - lowerBound]`

because the length of `primesInRange`

is only `upperBound - lowerBound + 1`

. For example, if `lowerBound`

is 28 and `upperBound`

is 40, then the length of `primesInRange`

is 13. This means that in `primesInRange`

, the index of 28 is 0, the index of 29 is 1, the index of 30 is 2, and so on. So when `potentialPrime`

is 30, we want to update the value at index 2 in `primesInRange`

. This is why we subtract `lowerBound`

from `potentialPrime`

so that we update the value at the correct index.

for (let potentialPrime = lowerMultiple; potentialPrime <= upperBound; potentialPrime = potentialPrime + prime) {primesInRange[potentialPrime - lowerBound] = false;}

With all of the non-prime numbers flagged in the `primesInRange`

array, we can now loop through the `primesInRange`

array and push all of the primes in the range `[lowerBound, upperBound]`

to the `finalPrimesInRange`

array.

Again, since the length of `primesInRange`

is `upperBound - lowerBound + 1`

, we want to adjust the index of the value that we are looking at in `primesInRange`

by subtracting `lowerBound`

from `i`

.

const finalPrimesInRange = [];for (let i = lowerBound; i <= upperBound; i++) {if (primesInRange[i - lowerBound]) {finalPrimesInRange.push(i);}}return finalPrimesInRange;

### Put it all together

So putting it all back together, our functions look like this:

// `getSmallPrimes` is an implementation of the Sieve of Eratosthenes algorithm, but using the square root of the upper bound as our limitfunction getSmallPrimes(upperBound) {const primesArr = [];const limit = Math.sqrt(upperBound);const primesBoolArr = Array(Math.floor(limit) + 1).fill(true);// start at 2 since we know 0 and 1 are not primefor (let i = 2; i <= limit; i++) {if (primesBoolArr[i]) {for (let j = i * i; j <= limit; j += i) {primesBoolArr[j] = false;}}}// start at 2 since we know 0 and 1 are not primefor (let k = 2; k <= limit; k++) {if (primesBoolArr[k]) {primesArr.push(k);}}return primesArr;}// Segmented sieve implementationfunction segmentedSieveGetPrimes({upperBound, lowerBound = 0}) {// `smallPrimes` has primes in range [2, sqrt(upperBound)]const smallPrimes = getSmallPrimes(upperBound);// Initializes an array `primesInRange` of boolean values,// representing whether each number in the range [lowerBound, upperBound] is prime.// Initially, all numbers are assumed to be prime.const primesInRange = Array(upperBound - lowerBound + 1).fill(true);for (let prime of smallPrimes) {// the first multiple of `prime` which is in range [lowerBound, upperBound]// for example: 3's first multiple in range [28,40] is 30let lowerMultiple = Math.floor(lowerBound / prime);// If `lowerMultiple` is less than or equal to 1,// set it to the first multiple of `prime` greater than or equal to `lowerBound`// If `lowerMultiple` is less than or equal to 1,// it means the largest multiple found is less than `lowerBound`.// In this case, we adjust it to the first multiple of `prime` that// is greater than or equal to `lowerBound`.if (lowerMultiple <= 1) {lowerMultiple = prime + prime;}// If `lowerBound` is not divisible by `prime`,// adjust `lowerMultiple` to the next multiple of `prime` after `lowerBound`else if ((lowerBound % prime) !== 0) {lowerMultiple = (lowerMultiple * prime) + prime;}// If `lowerBound` is divisible by `prime`, keep `lowerMultiple` as the first multiple of `prime` in the range `[lowerBound, upperBound]` (which in this case is the value of `lowerBound`)else {lowerMultiple = lowerMultiple * prime;}// marks multiples of `prime` as not prime in the range [low, high]// by setting corresponding values in the `primesInRange` array to `false`for (let j = lowerMultiple; j <= upperBound; j = j + prime) {primesInRange[j - lowerBound] = false;}}const finalPrimesInRange = [];for (let i = lowerBound > 1 ? lowerBound : 2; i <= upperBound; i++) {if (primesInRange[i - lowerBound]) {finalPrimesInRange.push(i);}}return finalPrimesInRange;}

### Time and space complexity

The time complexity of this segmented Sieve of Eratosthenes algorithm is the same as a regular Sieve of Eratosthenes algorithm, which is `O(n log log n)`

.

The space complexity is reduced to `O(sqrt(n))`

since we aren't storing every single number in the range. This is a nice improvement on the space complexity of a regular Sieve of Eratosthenes algorithm, which is `O(n)`

. However, this will still hit memory limitations for extremely large ranges due to the array of booleans that we are creating.

## One more optimization

We can take our segmented Sieve of Eratosthenes algorithem one step further by partitioning the range into smaller chunks. This will reduce the space complexity even further, but will increase the time complexity slightly due to an added loop.

First, let's modify `getSmallPrimes`

a bit to make it more reusable. We'll rename it to `getPrimes`

and have it accept a `num`

parameter. We'll assume that `num`

is already the integer that you want for the upper bound. This allows us to eliminate the `limit`

variable. I've highlighted the changed lines below:

1// `getPrimes` is an implementation of the Sieve of Eratosthenes algorithm2function getPrimes(num) {3 const primesArr = [];4 const primesBoolArr = Array(num + 1).fill(true);56 // start at 2 since we know 0 and 1 are not prime7 for (let i = 2; i <= num; i++) {8 if (primesBoolArr[i]) {9 for (let j = i * i; j <= num; j += i) {10 primesBoolArr[j] = false;11 }12 }13 }1415 // start at 2 since we know 0 and 1 are not prime16 for (let k = 2; k <= num; k++) {17 if (primesBoolArr[k]) {18 primesArr.push(k);19 }20 }2122 return primesArr;23}

Then we'll break the logic for the segmented Sieve of Eratosthenes algorithm into its own function so that we can call it for each chunk of the range. This is the same as the `getPrimes`

function we had in our first segmented sieve implementation, but we've removed the `smallPrimes`

calculation and are now passing it in as a parameter.

1function segmentedSieve({upperBound, lowerBound = 0, smallPrimes}) {2 // Initializes an array `primesInRange` of boolean values,3 // representing whether each number in the range [lowerBound, upperBound] is prime.4 // Initially, all numbers are assumed to be prime.5 const primesInRange = Array(upperBound - lowerBound + 1).fill(true);67 for (let prime of smallPrimes) {8 // the first multiple of `prime` which is in range [lowerBound, upperBound]9 // for example: 3's first multiple in range [28,40] is 3010 let lowerMultiple = Math.floor(lowerBound / prime);1112 // If `lowerMultiple` is less than or equal to 1,13 // set it to the first multiple of `prime` greater than or equal to `lowerBound`14 // If `lowerMultiple` is less than or equal to 1,15 // it means the largest multiple found is less than `lowerBound`.16 // In this case, we adjust it to the first multiple of `prime` that17 // is greater than or equal to `lowerBound`.18 if (lowerMultiple <= 1) {19 lowerMultiple = prime + prime;20 }2122 // If `lowerBound` is not divisible by `prime`,23 // adjust `lowerMultiple` to the next multiple of `prime` after `lowerBound`24 else if ((lowerBound % prime) !== 0) {25 lowerMultiple = (lowerMultiple * prime) + prime;26 }2728 // If `lowerBound` is divisible by `prime`, keep `lowerMultiple` as the first multiple of `prime` in the range `[lowerBound, upperBound]` (which in this case is the value of `lowerBound`)29 else {30 lowerMultiple = lowerMultiple * prime;31 }3233 // marks multiples of `prime` as not prime in the range [low, high]34 // by setting corresponding values in the `primesInRange` array to `false`35 for (let j = lowerMultiple; j <= upperBound; j = j + prime) {36 primesInRange[j - lowerBound] = false;37 }38 }3940 const finalPrimesInRange = [];41 for (let i = Math.max(2, lowerBound); i <= upperBound; i++) {42 if (primesInRange[i - lowerBound]) {43 finalPrimesInRange.push(i);44 }45 }4647 return finalPrimesInRange;48}

Finally, we'll create a new `getPrimesInRange`

function. This function gets all of the small primes in the range `[2, sqrt(upperBound)]`

, just like how we previously did in the original `getPrimes`

function. Then we divide the range `[Math.max(2, lowerBound), upperBound]`

into smaller segments of size `sqrt(upperBound)`

. For each of these segments, we call the `segmentedSieve`

function to find all of the primes in that segment. We then append these primes to the `doubleSegmentedSieveGetPrimes`

array and return it.

1function doubleSegmentedSieveGetPrimes({upperBound, lowerBound = 0}) {2 const sqrtUpperBound = Math.floor(Math.sqrt(upperBound));3 // `getPrimes` has primes in range [2, sqrtUpperBound]4 const smallPrimes = getPrimes(sqrtUpperBound);56 /*7 divide the range [Math.max(2, lowerBound), upperBound] into8 smaller segments of size sqrtUpperBound,9 use segmentedSieve to find all the10 primes in the segment range [l, r] and append11 to allPrimesInRange12 */13 const allPrimesInRange = [];1415 for (let i = Math.max(2, lowerBound); i <= upperBound; i += sqrtUpperBound) {16 const upper = Math.min(i + sqrtUpperBound - 1, upperBound);17 allPrimesInRange.push(...segmentedSieve({upperBound: upper, lowerBound: i, smallPrimes}));18 }1920 return allPrimesInRange;21}

## Checking differences in execution time

If you're curious as to just how much faster the segmented Sieve of Eratosthenes algorithm is from the regular one, you can use JavaScript's `performance.now()`

method to check the execution time of each algorithm.

You could use

`Date.now()`

instead, but I opted for`performance.now()`

. While`Date.now()`

is faster, it is only accurate to ~1ms, whereas`performance.now()`

is accurate to the microsecond. Depending on the size of the range that you are checking,`performance.now()`

can give you a more accurate representation of the execution time. You can read more about it on the MDN docs.

function checkExecutionTime(cb) {const t0 = performance.now();cb();const t1 = performance.now();console.log(`Call took ${t1 - t0} milliseconds.`);}// Brute forcecheckExecutionTime(() => bruteForceGetPrimes(100000));// My first optimizationcheckExecutionTime(() => firstOptimizationGetPrimes({ upperBound: 100000, lowerBound: 0 }));// Regular Sieve of EratosthenescheckExecutionTime(() => regularSieveGetPrimes(100000));// Segmented Sieve of EratosthenescheckExecutionTime(() => segmentedSieveGetPrimes({ upperBound: 100000, lowerBound: 0 }));// "Doubly" segmented Sieve of EratosthenesdoubleSegmentedSieveGetPrimes(() => getPrimes({ upperBound: 100000, lowerBound: 0 }));

Here are the results of the above code to check the execution time of each algorithm for a range of `[0, 100000]`

:

- Brute force algorithm -
`1346.300000011921`

milliseconds - First optimization -
`150.29999995231628`

milliseconds - Regular Sieve of Eratosthenes algorithm -
`4.900000035762787`

milliseconds - Segmented Sieve of Eratosthenes algorithm -
`1.0999999642372131`

milliseconds - "Doubly" segmented Sieve of Eratosthenes algorithm -
`1.699999988079071`

milliseconds

As you can see, the segmented Sieve of Eratosthenes algorithm is the fastest of all 5 solutions. The "doubly" segmented Sieve of Eratosthenes is tad slower due to the extra looping to partition the range into smaller segments. And the regular Sieve of Eratosthenes algorithm is the slowest of the three sieves. However, all three sieves are much faster than the brute force algorithm and my first optimization.

## Summary

To recap, the Sieve of Eratosthenes algorithm is a way to find all prime numbers up to a given number. It works by starting with a list of all numbers up to the given number, and then removing all multiples of each number in the list. The numbers that are left are prime numbers.

In a segmented sieve, we use the Sieve of Eratosthenes algorithm, but we only store the primes up to the square root of the upper bound. We then use those primes to find the primes in the range `[lowerBound, upperBound]`

. This reduces the space complexity of the algorithm from `O(n)`

to `O(sqrt(n))`

to make it more memory efficient.

If we want to further optimize the space complexitiy of the segmented sieve, we can partition the range `[lowerBound, upperBound]`

into smaller segments of size `sqrt(upperBound)`

. We can then use the segmented sieve to find the primes in each of these segments. This reduces the space complexity of the algorithm, but also *slightly* increases the time complexity.