为什么这些筛选优化会破坏我的代码？

Question

我怎样才能使它们正常工作？我正在尝试根据之前的建议优化我的筛子，但在这两种情况下代码都会中断：

递增 j = j + ( i * 2) 会破坏代码。

显然我和其他人一样缺少一些关于优化的概念。但总的来说，您只需遍历并将素数的所有倍数标记为非素数。下一步是优化。

// 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]) {
      // recommended optimization breaks the code
      // 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));

Answer 1

实际上优化对我有用：

 // 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 )'optimization'实际上破坏了算法。结果将包含非质数。这里有一个要检查的片段：

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));

Answer 2

您的优化需要先去掉偶数（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 倍。

The code although works, seems put too much tricks to do and introduced both extra calculations and confusion. A simple sieve code like the following in my comparison out performs the one in the answer. Again, KISS is the principle.

It took the script in the origin answer 317ms to sieve 1M numbers, while the simple sieve took only 241ms.

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);
}

Answer 3

你犯了一个简单的错误，没有准备好你的筛子。您应该消除所有 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

为什么这些筛选优化会破坏我的代码？

Why are these sieve optimizations breaking my code?

javascript

primes

sieve

sieve-of-eratosthenes

编辑

编辑 2