为什么我的筛子不能很好地找到素数？

Question

我编写了两个主要查找器功能，而筛子的性能仅好10％。我对简单版本使用了两种优化方法。

• 不检查偶数
• 仅检查平方根或j * j <= i。 （等效）

以及对筛版的一种优化

• 仅检查平方根或i * i <= n。 （等效）

我可以添加到筛子的哪些优化？

我的筛子非常慢。我现在还不想做按位的实现，我想了解这种实现是否带来任何好处。

或者如果我错过了实现点。

伪代码中的内部for循环在这里看起来很有趣/很奇怪

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

我不知道该怎么解释。

这里是：

算法 Eratosthenes筛子is：

input：整数n> 1。输出：从2到n的所有素数。let A是Boolean数组值，由integers 2到n进行索引，最初所有set到true。for i = 2，3，4，...，不超过√ndo如果 A [i] 是真的for j = i 2，i 2 + i，i 2 + 2i，i 2 + 3i，... ，不超过n doA [j]：= falsereturn所有i，使得A [i]为true。 

// prime-2
// 2 optimizations - odds and square root
function prime2(n){
  const primes = [2];
  not_prime: for(let i = 3; i < n; i += 2){
    for(let j = 2; j * j <= i; j++){
      if(i % j === 0){
        continue not_prime;
      }
    }
    primes.push(i);
  }
  return primes;
}

// prime-3
// sieve implementation
function prime3 (n) {
  const primes = [];
  const sieve = (new Array(n)).fill(true);
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      for (let j = i + i; j < n; j += i) {
        sieve[j] = false;
      }
    }
  }
  makePrimes(sieve, primes, n);
  return primes;
};
function makePrimes(sieve, primes, n){
  for (let i = 2; i < n; i++) {
    if(sieve[i]) {
      primes.push(i);
    }
  }
}

Answer 1

您所看到的是理论运行时复杂度差异的表达，即两种算法之间的真正算法差异。

最佳试验分割筛的复杂度为O（n ^1.5 /（log n）²），而Eratosthenes筛的复杂度为O（n log log n）] >> 。

根据Scott Sauyet在the comments中发布的经验运行时间数据，>]

   1e6      279ms      36ms
   1e7     6946ms     291ms
   -------------------------
   n^       1.40       0.91
[empirical orders of growth
在测量范围内大致为〜n 1.4

和〜n，非常合适。