算法 "Sieve of Eratosthenes" javascript

Question

埃拉托色尼筛法示例实现中的代码是？
这个实现的复杂性是什么？

更新：我用一个数组项构建了一个计数操作图表。我认为复杂性是 O(n)。我对吗？

console.time('exec');
var arr = fn(Math.pow(10, 2));
console.timeEnd('exec');

function fn(n) {
    var arr = Array.apply(null, {length: n + 1}).map(function() {return true;});
    arr[0] = arr[1] = false;
    var base = 2;
    while (Math.pow(base, 2) < n) {
        var counter = 2;
        while (counter * base < n) {
            arr[counter * base] = false;
            counter++;
        }
        base++;
    }
    return arr;
}

// show result
arr.forEach(function(item, index) {
  if (item) {
     console.log(index);
  }
});

Answer 1

运行时复杂度为 O(n*n)，因为您迭代 base 并计算到想要的值 n（您错过了循环比较中的最后一个值）。

console.time('exec');

function fn(n) {
    var arr = Array.from({ length: n + 1 }, (_, i) => i > 1),
        base = 2,
        counter;

    while (Math.pow(base, 2) <= n) {
        counter = 2;
        while (counter * base <= n) {
            arr[counter * base] = false;
            counter++;
        }
        base++;
    }
    return arr;
}

var arr = fn(Math.pow(10, 2));

console.timeEnd('exec');
// show result
arr.forEach(function(item, index) {
  if (item) {
     console.log(index);
  }
});

Answer 2

算法的渐近时间复杂度我认为是O(n log n).

外循环运行 2 ... sqrt(n)。内部循环运行 n / base 次，其中 base 在 2 ... sqrt(n).

的外部运行ge

运行循环产生的总迭代次数可以表示为：

(1) (n / 2) + (n / 3) + (n / 4) + ... + (n / sqrt(n))

上面的括号用于表示在外循环的单次迭代中内循环的迭代次数。

我们可以提取n并得到

(2) n * (1/2 + 1/3 + 1/4 + ... + 1 / sqrt(n))

括号中的项是调和级数，众所周知它是发散的，所以我们没有得到像 O(1)[=95= 这样好的东西] 那里，虽然发散极慢。你的图表也从经验上证明了这一点，它看起来是线性的。

表明调和级数与ln(n)(source)有常数关系。

因此，我们得到 n * ln(n)，因此复杂度为 O(n log n).

你没有得到更好的 O(n log log n) 复杂性，因为您的解决方案不使用素数分解（因此素数调和级数为 O(log log n) (source)).

实际上，这是因为您的算法检查非素数，例如arr[counter * base] = false; 中的相同索引分配给 base 和 counter 对 {2, 6}, {3, 4}, {4, 3}, {6, 2}，但 base 4 和 6 在应用时已知不是素数，根据算法的定义，它们的所有倍数也已知不是素数，因此再次检查它们是没有用的。

编辑

一个O(n日志日志n) JavaScript 实现可能如下所示：

function sieve(n) { // primes[x] contains a bool whether x is a prime const primes = new Array(n + 1).fill(true); // 0 and 1 are not primes by definition primes[0] = false; primes[1] = false; function square(i) { return i * i; } for (let number = 2; square(number) <= n; number += 1) { if (!primes[number]) { // we have already determined that the number is not a prime // therefore all its multiples are also already determined not to be primes // skip it continue; } for (let multiplier = 2; multiplier * number <= n; multiplier += 1) { // a multiple of prime is not a prime primes[multiplier * number] = false; } } return primes; }

这样的算法仍然运行外循环 sqrt(n) 次，但内循环现在不是针对每个数字运行而是只针对素数，所以对于 (2) 我们现在得到

(2a) n * (1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / (last_prime_less_or_equal_sqrt(n))

如前所述，括号中的项是log log n增长的素谐波序列。这让我们到达 O(n log log n) 乘以 n.

Answer 3

@ZdeněkJelínek，@NinaScholz，感谢您的帮助。这是根据您的建议编写的代码。
最后，希望我能够以复杂度 O(n log log n) 来实现它。

console.time('exec');
var arr = fn(Math.pow(10, 5));

function fn(n) {
  var arr = Array.apply(null, {
    length: n + 1
  }).map(function(_, i) {
    return i > 1;
  });
  var base = 2;
  while (Math.pow(base, 2) < n) {
    var counter = 2;
    while (counter * base <= n) {
      arr[counter * base] = false;
      do {
        counter++;
      } while (!arr[base]);
    }
    do {
      base++;
    } while (!arr[base]);
  }
  return arr;
}
console.timeEnd('exec');
console.log('array length: ' + arr.length);

// show result
/*
arr.forEach(function(item, index) {
  if (item) {
    console.log(index);
  }
});
*/

算法 "Sieve of Eratosthenes" javascript

Algorithm "Sieve of Eratosthenes" by javascript

javascript

sieve-of-eratosthenes