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

Question

我一直在研究欧拉计划问题，在解决问题 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.188 毫秒，这实际上是我的第二个版本的程序。

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

i <= primes.length

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

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

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

有没有人对此有任何见解？

Answer 1

您的外循环迭代了 775146 次。那是 600851475143 的平方根。您的内循环至少迭代 5 次并增加。所以迭代的总数至少是 3875730。这需要一段时间。

尝试插入您的内循环进入次数的计数。该计数将与代码的运行时间成正比。