Code Review: Prime Number Function

Hello, I am wrapping up the Full Stack Engineer Career Path and I was wondering if someone could do a code review on my function that I wrote. It is called the Sieve of Eratosthenes, and is a function which given an number input will return all prime numbers up to (and including) that input.

Here is the code:

const sieveOfEratosthenes = (limit) => {
  const numbers = new Array(limit + 1).fill(true);
  numbers[0] = false;
  numbers[1] = false;
  
  for (let i = 2; i <= limit; i++) {
    if (numbers[i] === true) {
      for (let j = i * 2; j <= limit; j = j + i) {
        numbers[j] = false;
      }
    }
  }

  const results = [];

  for(let i = 0; i < numbers.length; i++) {
    if (numbers[i] === true) {
      results.push(i);
    }
  }
  return results;
}

const test = sieveOfEratosthenes(13);
// should return [2, 3, 5, 7, 11, 13]
console.log(test);

// Leave this line for testing:
module.exports = sieveOfEratosthenes;

Only thing I would change is that line (in both places). Given we know that all the elements are boolean (since we built it that way) all we need to do in that expression is test for truthiness, not compare to the boolean.

if (numbers[i]) {

}

In six months time, without checking your notes, sit down and write this algorithm from scratch. There can be no better test of our understanding and algorithm ability than working with the problem, from scratch. I have never seen any learner write this algorithm from scratch. Why would they when they have source code right there for the searching from which to learn? The proof is in the pudding. It is okay to learn from other’s code, so long as one actually learns and is able to begin thinking for themselves.

1 Like

Thank you for the review and the insights, mtf!

1 Like

Logic looks solid.

You can generate results with a .filter.

You can check if numbers[j] is already false before you set it.

Ok, I feel I should show the filter thing. Not as obvious as I initially thought…

return numbers.map((x, i) => x ? i : undefined).filter(x => x != undefined);

Looking back on that, a reduce is probably cleaner:

return numbers.reduce((acc, x, i) => x ? [...acc, i] : acc, []);
1 Like

Thanks for the review baavgai! I think that using a reduce does make the code look cleaner, too.