javascript - JavaScript中的Eratosthenes算法筛网无休止地大量运行

我一直在尝试用JavaScript编写Sieve of Eratosthenes算法。基本上我只是按照以下步骤操作:

创建一个从2到(n-1)的连续整数列表

令第一个质数p等于2

从p开始，以p为增量递增，并删除这些数字(p和p的倍数)中的每一个

转到列表中的下一个数字，然后重复2,3,4

将无意删除的素数添加回列表

这就是我想出的:

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中)，但仍然无法完全理解它。

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

最佳答案

您将通过使用线性操作的数组操纵函数(例如Array#indexOf和Array#splice)来使Eratosthenes筛子的速度大大降低。当您可以同时为两个操作使用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.