大量的 for 循环加载时间太长

Question

我正在开发一个旨在生成素数的程序，我正试图找到第 10001 个素数。每次循环运行时，它都会测试变量 i 以查看它是否可以被变量 j 整除，变量 j 是另一个循环的一部分，该循环达到 i 的一半。如果 i 可以被 j 整除，那么它会将 1 加到变量 prime 上，当循环完成后，它会检查变量 prime 是否大于 2；如果是，则 i 不是素数。如果它是质数，它会被 push() 到存储所有质数的变量数组。对不起，如果这有点令人困惑。

我的问题是，尽管此代码有效，但每当我将第一个 for 循环设置得太高时（这里我将其设置为 100000），我的浏览器就会冻结：

var prime = 0;
var array = [];
for(var i = 2; i <= 100000; i+=1) {
  var prime = 0;
  for(var j = 0; j <= i/2; j+=1) {
    if(i % j === 0) {
      prime += 1;
    }
  }

  if(prime < 2) {
    array.push(i);
  }
}

console.log(array.length)

我知道我可以复制并粘贴所有质数，但我想让程序运行。有什么想法可以让程序停止冻结吗？

Answer 1

这是因为你的算法的时间复杂度几乎是 O(n^2)。 Sieve of Eratosthenes 创建了一个更好的算法，可以防止您的浏览器冻结。这是一种方法：

var exceptions = {
  2: 2,
  3: 3,
  5: 5,
  7: 7
}

var primeSieve = function (start, end) {
  var result = [];
  for (start; start < end; start++) {
    if (start in exceptions) result.push(start);
    if (start > 1 && start % 2 !== 0 && start % 3 !== 0 && start % 5 !== 0 && start % 7 !== 0) {
      result.push(start);
    }
  }
  return result;
};

你显然可以让这个看起来更漂亮，但我只是做的很快，这样你就明白了。我希望这有帮助！如果您还有其他问题，请告诉我。

大量的 for 循环加载时间太长

Massive for loop taking too long to load

javascript

primes

for-loop