javascript - Math.sqrt(n) 与用于查找 N 个素数的埃拉托色尼算法相关的函数是什么？

Question

我的标题措辞正确吗？

var eratosthenes = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];
    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) 
        array.push(true);
    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) 
                array[j] = false;
        }
    }
    for (var i = 2; i < n; i++) {
        if(array[i])
            output.push(i);
    }
    return output;
}

fiddle :http://jsfiddle.net/KARZw/

upperLimit = Math.sqrt(n) 的用途是什么？

代码来自:Sieve of Eratosthenes algorithm in JavaScript running endless for large number

Answer 1

数字的最大可能因数是它的平方根。

取17。这是素数吗？您可以天真地寻找 1...17 中的所有因数，或者可以取平方根并从 2-4 中寻找，因为在 4 之后，实际上就没有任何新的可能因数了。

添加更多细节。

让我们看一下简单的模型(是的，不需要检查偶数，因为我们知道它不是偶数，但这非常简单):

Is 17 divisible by 2?  No
Is 17 divisible by 3?  No
Is 17 divisible by 4?  No 
Is 17 divisible by 5?  No
Is 17 divisible by 6?  No
Is 17 divisible by 7?  No 
....
Is 17 divisible by 16?  No 

17 是素数。

现在，假设您使用平方根的上限。

is 17 divisible by 2?  If it was, it would be 2 x 8 or 2 x 9.
is 17 divisible by 3?  If it was, it would be 3 x 5 or 3 x 16.
is 17 divisible by 4?  If it was, it would be 4 x 4 or 4 x 5.

现在看看当你达到 5 时会发生什么？您基本上只是转换了这些因素。

17能被5整除吗？如果是的话，那就是 5x3 或 5x4。好吧，这些已经被“17 能被 3 整除”和“17 能被 4 整除”涵盖了

相同的模式会重复到朴素模型的末尾。

因此，一旦您检查了直到该数字的平方根为止的所有可能因数，您就已经检查了该数字的所有可能因数。