javascript - 为什么这个for循环要花这么长时间？

我一直在研究欧拉计画的问题，在解决问题3时遇到了一些奇怪的事情。

问题3要求您“查找数字600851475143中的最大素数”

我这样解决了:

var search = 600851475143;
var highest = 0;
var primes = [2,3,5,7,11];

function isPrime(num) {
    for (var i = 0; i < primes.length; i++) {
        if (num === primes[i]) {
            return true;
        }
        else if (num % primes[i] === 0) {
            return false;
        }
    }
    primes.push(num);
    return true;
}


for (var n = 2; n <= Math.floor(Math.sqrt(search)); n++) {
    if (isPrime(n) && search % n === 0) {
        highest = n;
    }
}

console.log(highest);

这花了7534.188ms，这实际上是我的第二个程序版本。

在第一个版本中，唯一的区别是isPrime函数中的for循环中声明了

i <= primes.length

进行此更改后，程序耗时72084.540毫秒

从大约8秒增加到大约72秒，慢了9倍。

我不认为额外的迭代会导致时间的增加。我最初的想法是，因为它正在寻找不存在的索引，但是可以肯定的是，这会使程序崩溃，而不仅仅是导致它运行缓慢。

有人对此有任何见识吗？

最佳答案

您的问题可能是由于以下事实造成的:在Javascript中，以下代码:

var primes = [2,3,5,7,11];
console.log(primes[12]);

产生输出undefined，即使primes[12]不在数组的范围之内。

在这方面，Javascript与其他语言不一样-超出数组范围不会导致崩溃，但是会返回未定义的值，并允许程序继续运行。 undefined是可以存储在变量中的实际值，因此它将继续评估if语句并在上一次迭代后退出循环。

至少在Chrome中，与undefined的比较比较慢。 See this Stackoverflow question for some performance information。