javascript - 算法 "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 log n)。

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

运行循环的总迭代次数可以表示为:

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

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

我们可以提取n并得到

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

括号中的项是已知发散的调和级数，所以我们没有得到像 O(1) 这样的好东西，尽管发散非常大慢的。您的线性图表也从经验上证明了这一点。

表明调和级数与 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 log log 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.