Почему эта ситовая оптимизация нарушает мой код?

Вы совершили простую ошибку, не подготовив сито. Для начала вам следует исключить все числа, кратные 2:

function makeSieve(n){
  const sieve = new Array(n).fill(true);
  for(let i = 2; i < sieve.length; i += 2){
    sieve[i] = false;
  }
}

Теперь, когда вы переходите к отметке непростых чисел, вы можете увеличивать i * 2

Например

3, 6, 9, 12, 15, 18, 21

станет

3, 9, 15, 21

Ваша оптимизация должна применяться после того, как сначала нужно избавиться от четного числа (кроме 2). потому что, когда i==2, вы фактически пропускали все четные числа, увеличивая на i*2.

Вот рабочий код:

// prime-3
// sieve implementation
function prime3(n) {
  let sieve = (new Array(n)).fill(true);
  for (let i = 4; i < n; i+=2) {
    sieve[i] = false;
  }
  
  // Only iterate up to the square root n for marking
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      // now it works
      // j = j + ( i * 2 )
      for (let j = i * i; j <= n; j = j + i*2) {
        sieve[j] = false;
      }
    }
  }
  return makePrimes(sieve, n);
};

function makePrimes(sieve, n) {
  let primes = [];
  for (let i = 2; i < n; i++) {
    if (sieve[i]) {
      primes.push(i);
    }
  }
  return primes;
}
console.log(prime3(100));

Редактировать

Поцарапайте это. Дальнейшее тестирование действительно показывает, что prime3 в 3 раза быстрее, чем простое сито.

Код хоть и работает, но, кажется, вложил в него слишком много уловок и внес как дополнительные вычисления, так и путаницу. Простой код сита, подобный приведенному ниже в моем сравнении, выполняет код в ответе. Опять же, KISS - это принцип.

Сценарию в исходном ответе потребовалось 317 мсек, чтобы просеять 1 млн чисел, в то время как простое сито заняло всего 241 мс.

function simpleSieve(n) {
  let a = new Array(n)
  let answer = []
  let p
  for (let i = 2; i < n; i ++) {
    a[i] = i
  }
  for (let i = 2; i < n; i++) {
    if (a[i]) {
      answer.push(a[i])
      p = a[i]
      for(let j = p; j < n;  j += p) {
        a[j] = 0
      }
    }
  }
  return answer
}

Редактировать 2

Повторное тестирование с cpp и prime3 действительно улучшает примерно в 3 раза быстрее, чем простое сито:

p3:
n = 100000000, t = 866717 microseconds.
n = 200000000, t = 2354425 microseconds.
n = 300000000, t = 3689165 microseconds.
n = 400000000, t = 4950224 microseconds.
n = 500000000, t = 6119779 microseconds.
n = 600000000, t = 7375925 microseconds.
n = 700000000, t = 8647293 microseconds.
n = 800000000, t = 10477116 microseconds.
n = 900000000, t = 11589894 microseconds.
n = 1000000000, t = 12806997 microseconds.
simple:
n = 100000000, t = 2316019 microseconds.
n = 200000000, t = 6063749 microseconds.
n = 300000000, t = 9783295 microseconds.
n = 400000000, t = 13315450 microseconds.
n = 500000000, t = 16640474 microseconds.
n = 600000000, t = 20282461 microseconds.
n = 700000000, t = 24219469 microseconds.
n = 800000000, t = 29203786 microseconds.
n = 900000000, t = 32965856 microseconds.
n = 1000000000, t = 37694084 microseconds.

Коды здесь для полноты:

void simpleSieve(int n) {
  bool *a = (bool *)calloc(n, sizeof(bool));
  int p;
  memset(a, true, sizeof(bool) * n);
  for (int i = 2; i < n; i++) {
    if (a[i]) {
      p = i;
      for (int j = p; j < n; j += p) {
        a[j] = 0;
      }
    }
  }
  free(a);
}

void prime3(int n) {
  bool *sieve = (bool*)calloc(n, sizeof(bool));
  sieve[2] = true;
  for (int i = 3; i < n; i+=2) {
    sieve[i] = true;
  }
  int step;
  for (int i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      step = i*2;
      for (int j = i * i; j <= n; j = j + step) {
        sieve[j] = false;
      }
    }
  }
  free(sieve);
}

Собственно оптимизация у меня работает:

 // prime-3
    // sieve implementation
    function prime3 (n) {
      const sieve = (new Array(n)).fill(true);
    
      // Only iterate up to the square root n for marking
      for (let i = 2; i * i <= n; i += 1) {
        if (sieve[i]) {
    
          // recomended optimizations break the code
          // j = i * i 
          // j = j + ( i * 2 )
          for (let j = i * i; j <= n; j = j+i) {
            sieve[j] = false;
          }
        }
      }
      return makePrimes(sieve, n);
    };
    
    function makePrimes(sieve, n){
      let primes = [];
      for (let i = 2; i < n; i++) {
        if(sieve[i]) {
          primes.push(i);
        }
      }
      return primes;
    }
    
    console.log(prime3(100));

Но ваша j = j + ( i * 2 ) «оптимизация» на самом деле нарушает алгоритм. Результаты будут содержать не простые числа. Вот фрагмент для проверки:

function prime3 (n) {
      const sieve = (new Array(n)).fill(true);
    
      // Only iterate up to the square root n for marking
      for (let i = 2; i * i <= n; i += 1) {
        if (sieve[i]) {
    
          // recomended optimizations break the code
          // j = i * i 
          // j = j + ( i * 2 )
          for (let j = i * i; j <= n; j = j+(i*2)) {
            sieve[j] = false;
          }
        }
      }
      return makePrimes(sieve, n);
    };
    
    function makePrimes(sieve, n){
      let primes = [];
      for (let i = 2; i < n; i++) {
        if(sieve[i]) {
          primes.push(i);
        }
      }
      return primes;
    }
    
    console.log(prime3(100));