If statement involving modulo behaving erratically

Question

I'm making a function to create a list of prime numbers from 0 to num. I start off with a list of integers from 2 to num, and iterate over each one that goes from 2 to i < num; if at any point item % i === 0, the item is removed from the list. This works fine:

function getPrimes(num) {
  // get list of ints from 2 to num
  let primes = [...Array(num + 1).keys()];
  primes = primes.splice(2);
  let lastNumber = primes[primes.length - 1];
  // make iterable, run its loop
  // for each number in primes
  for (let number of primes) {
    // use iterable to remove if not prime
    for (let i = 2; i < num; i++) {
      if (number % i === 0) {
        primes.splice(primes.indexOf(number), 1);
      }
    }
  }
  // add back two
  primes.unshift(2);
  return primes;

But when I try and make the iterable for each number only to up to Math.floor(num / 2) for the sake of efficiency, it breaks the code somehow:

function getPrimes(num) {
  // get list of ints from 2 to num
  let primes = [...Array(num + 1).keys()];
  primes = primes.splice(2);
  let lastNumber = primes[primes.length - 1];
  // make iterable, run its loop
  // for each number in primes
  for (let number of primes) {
    // use iterable to remove if not prime
    for (let i = 2; i < Math.floor(num / 2); i++) {
      if (number % i === 0) {
        primes.splice(primes.indexOf(number), 1);
      }
    }
  }
  // add back two
  primes.unshift(2);
  return primes;

When I tried it out, getPrimes(10) gives me [ 2, 3, 5 ]. So seven is missing from the list of prime numbers from 0 to 10. Why is that? I checked and 7 modulo 2, 3, and 4 returns 1, 1, and 3, respectively. So why is the code in the loop running that removes 7 from primes? It's the only place in the code where I put that I wanted to remove a number from the array.

If you splice an array as you're iterating over it, you can expect elements to be skipped and other unpredictable behavior. Iterating backwards would avoid issues in this case where the element removed will never affect the remaining items left to be traversed in the array. Also, if you have the index, you can avoid the linear `indexOf` call. — ggorlen, Jul 24 '20 at 15:04

score 1 · Accepted Answer · answered Jul 24 '20 at 15:12

The first issue is that you are looping while removing items, which causes some items to be skipped. Loop backwards instead, so that only items that have already been checked are shifted. Second, num / 2 should be changed to Math.sqrt(number), as that is the maximum factor that needs to be checked before we can be sure that a number is prime. With this method, there is no need to add 2 back to the array.

function getPrimes(num) {
  // get list of ints from 2 to num
  let primes = [...Array(num + 1).keys()];
  primes = primes.splice(2);
  let lastNumber = primes[primes.length - 1];
  // make iterable, run its loop
  // for each number in primes
  for(let i = primes.length - 1; i >= 0; i--){
    let number = primes[i];
    // use iterable to remove if not prime
    for (let j = 2; j * j <= number; j++) {
      if (number % j === 0) {
        primes.splice(i, 1);
        break;
      }
    }
  }
  return primes;
}
console.log(...getPrimes(10));

If statement involving modulo behaving erratically

1 Answers1