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

Question

我写了两个素数查找器函数，但筛子的性能只提高了大约 10%。我对简单版本使用了两个优化。

不检查偶数
只检查平方根或 j * j <= i。（相当于）

和筛版本的一项优化

只检查平方根或i * i <= n。（相当于）

我可以对筛子进行哪些优化？

我的筛子很慢。我还不想按位实现，我想了解这种实现是否有任何好处。

或者如果我错过了一个实施点。

此处伪代码中的内部 for 循环看起来很有趣/很奇怪

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

不知道怎么解读。（更新： OP 似乎在评论中指出，从维基百科复制粘贴伪代码后，格式不正确是一个问题，现在格式更正后就很清楚了）

这里是：

algorithm Sieve of Eratosthenes is:

input: an integer n > 1.
output: all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n do
    if A[i] is true
        for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n do
            A[j] := false

return all i such that A[i] is 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)²)^(*) 而 sieve of Eratosthenes' 的复杂度是 O(n log log n).

根据 Scott Sauyet in 、

发布的经验运行时间数据

   1e6      279ms      36ms
   1e7     6946ms     291ms
   -------------------------
   n^       1.40       0.91

empirical orders of growth大致是~n^1.4和~n测量范围，很合适。

所以您的 genuine sieve does perform well. The trial division 筛子按预期执行。如果我们足够大地增加问题规模，代码的算法性质将始终击败任何存在或 不存在 的任何二次优化。

通过仅在一个问题大小的点上测量它们来比较性能是永远不够的。因此，即使您只看到 "simpler one" 的 10% 差异，如果您以更大的尺寸进行测试，差异也会更大。

如果您想要一些关于可以进一步改进代码的指示，请注意，对于初学者，您从 i+i 而不是 i*i 开始内部循环。

另一种常见的优化是针对特例 2，从 3 开始，将候选者递增 2 并使用 2*i 的内循环增量而不是 i，以实现即时 2 倍加速.这是最简单的 wheel factorization 优化形式，可以进一步应用，但对于每个额外的素数递减 returns 。但是使用 2-3-5-7 是很常见的，如果有记忆的话，应该会再提供大约 2 倍的加速。

最后但同样重要的是， segmented。

^(*) 那是 π(n)* π(√n) coming from primes, and ，来自复合材料。

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

Why does my sieve not perform well for finding primes?

javascript

optimization

performance

primes

time-complexity