我一直在努力写Sieve of Eratosthenes JavaScript 中的算法。基本上我只是按照以下步骤操作:
- 创建一个从 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中)但仍然不能完全理解它。
问题:如何使这项工作适用于足够大的数字,例如 100 万及以上?
最佳答案
通过使用线性时间运行的数组操作函数,例如 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;
};
关于javascript - JavaScript 中的 Eratosthenes 算法的筛法为大量运行无穷无尽,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15471291/