1

我在 javascript/node 上很新，我被困在一个我必须找到素数的问题上。我认为我的逻辑是正确的，但它产生了额外的数字。这是代码现在我使用从 2 到 100 的数组。谢谢提前

var num = [2];
for (var i = 3; i < 101; i++){
  num.push(i);
}

for(i = 0; i <= num.length; i++){
  for(var k = 2; k <= i; k++){
    if( (num[i] % k) == 0){
      num.splice(i, 1);
    }
  }
}

var fs = require('fs');
var outfile = "hel.txt";
fs.writeFileSync(outfile, num);
4

2 回答 2

8

陈述“但它正在产生额外的数字”并不完全正确。您在开始时生成了包含最多 100 的所有数字的数组。问题是并非所有非质数都被删除。

为什么？因为您在迭代数组时正在修改数组。结果是某些条目不会被检查，它们将被跳过。

例子：

想象一下数组

var num = [2,3,4,5,6,7,8,9,10,11];

Let ibe 7，所以我们正在测试num[7] = 9。9不是素数，因此它从数组中删除，然后看起来像

var num = [2,3,4,5,6,7,8,10,11];

在下一次迭代i中8，我们正在测试num[8] = 11。注意如何10没有测试？最初10是在 index8但由于我们删除9了 ，它的新索引是7，我们已经测试过了。数组的大小发生了变化，“右侧”的所有元素9都向左移动了一个位置。

为了解决这个问题，您可以以相反的顺序遍历数组（我也认为k <= i应该是k < num[i]）：

for (i = num.length - 1; i > -1; i--) {
  var n = num[i];
  for (var k = 2; k < n; k++) {
    if ((n % k) == 0) {
      num.splice(i, 1);
      break; // you can stop testing after you found a factor
    }
  }
}

对您的算法的小建议：仅测试高达数字平方根的因子就足够了，即：

for (var k = 2, r = Math.sqrt(n); k <= r; k++) {
    if ((n % k) == 0) {
      num.splice(i, 1);
      break;
    }
}

可能还有其他可能的改进，请查看http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。

于 2013-06-27T12:20:59.400 回答
2

尝试这个：

 for(i = num.length; i >= 0; i--){
    findFactors: for(var k =2; k <= i; k++){
        if(num[i]%k ==0){
             num.splice(i,1);
             break findFactors;
        }
    }

我还没有测试它，所以不确定它是否有效......

于 2013-06-27T12:20:45.407 回答