埃拉托色尼算法在JavaScript中筛运行无穷无尽的大量 [英] Sieve of Eratosthenes algorithm in JavaScript running endless for large number

问题描述

我一直在试图写的埃拉托色尼算法在JavaScript 筛。基本上，我只是从字面上遵循以下步骤：

I have been trying to write Sieve of Eratosthenes algorithm in JavaScript. Basically I just literally followed the steps below:

1. 从2创建连续整数名单到（n-1）
2. 首先让素数p等于2
3. 从对开始，计数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的测试和过程似乎只是无止境的，没有表现出内存不足的错误了。我在这里读解（也是在JavaScript），但仍不能完全融为一体prehend它。

It works for small numbers but not for numbers larger than one million. I used Node.js to test and the process just seems endless and no memory error shown up. I've read a solution here(also in javascript) but still cannot fully comprehend it.

问：如何使这项工作足够大的数字，例如一百万以上

Question: How to make this work for sufficiently large numbers such as one million and above?

推荐答案

您正在埃拉托色尼的筛故意利用数组操作功能，如阵列＃的indexOf 和阵列＃接续其中以线性时间运行。当你可以有O（1）这两种操作参与。

You are making the Sieve of Eratosthenes intentionally slower by making use of array manipulation functions such as Array#indexOf and Array#splice which runs in linear time. When you can have O(1) for both operations involved.

下面是埃拉托色尼的筛下传统的编程实践：

Below is the Sieve of Eratosthenes following conventional programming practices:

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

你可以看到一个活生生的例子了 N = 1 000 000 这里

这篇关于埃拉托色尼算法在JavaScript中筛运行无穷无尽的大量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！