javascript - JavaScript 中的 Eratosthenes 算法的筛法为大量运行无穷无尽

Question

我一直在努力写Sieve of Eratosthenes JavaScript 中的算法。基本上我只是按照以下步骤操作:

1. 创建一个从 2 到 (n-1) 的连续整数列表
2. 令第一个素数p等于2
3. 从 p 开始，以 p 为增量递增计数并删除每个数字(p 和 p 的倍数)
4. 转到列表中的下一个数字并重复 2、3、4
5. 将无意中删除的素数添加回列表

这就是我想出的:

function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];

// Eratosthenes algorithm to find all primes under n

// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
    array.push(i);
}

// Remove multiples of primes starting from 2, 3, 5,...
for(var i = array[0]; i < upperLimit; i = array[0]){
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){
        var index = array.indexOf(j);
        if(index === -1)
            continue removeMultiples;
        else
            array.splice(index,1);
    }
    tmpArray.push(k);
}
array.unshift(tmpArray);
return array;
}

它适用于较小的数字，但不适用于大于一百万的数字。我使用 Node.js 进行测试，这个过程似乎无穷无尽，没有出现内存错误。我读过一个解决方案 here (也在javascript中)但仍然不能完全理解它。

问题:如何使这项工作适用于足够大的数字，例如 100 万及以上？

Answer 1

通过使用线性时间运行的数组操作函数，例如 Array#indexOf 和 Array#splice，您正在使埃拉托色尼筛法变慢。当您可以将 O(1) 用于所涉及的两个操作时。

下面是遵循传统编程实践的 Eratosthenes 筛法:

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

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

You can see a live example for n = 1 000 000 here.