0

我用对了那个标题吗？

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;
}

小提琴：http: //jsfiddle.net/KARZw/

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

代码来自：JavaScript 中 Eratosthenes 算法的筛选，大量运行无休止

4

2 回答 2

3

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

拿 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 整除”所涵盖

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

所以，一旦你检查了所有可能的因素，直到数字的平方根，你就检查了这个数字的所有可能的因素。

于 2013-07-11T16:29:56.747 回答
1

一个数的平方根是它的一对素因数中最大的可能成员。

任何大于平方根的素数都需要乘以小于平方根的素数才能得到数字。

于 2013-07-11T16:28:06.903 回答