javascript - 同一件事的两个功能，一个崩溃，另一个不崩溃，为什么？

Question

我想要一个名为 findFirst 的函数，它接受参数 n 和 q，并返回除以 n 且大于或等于 q 的最小素数。所以首先我写了一个函数来判断一个数是否为质数。

var isPrime = function(n){
    if(n === 1){
        return false;
    }
    else if (n === 2 || n === 3){
        return true;
    }
    else {
        for(i=2; i < n; i++){
            if(i * i >= n){
            for(j=2; j<=i; j++){
                    if(n % j === 0){
                        return false;
                    }
                }
            return true;
            } 
        }
    }
};

可能还有其他方法可以提高效率，但我很确定这个函数不是问题。

所以有了这个函数，我第一次尝试编写 findFirst:

var findFirst = function(n,q){
    var p = q;
        while(n % p !== 0 || isPrime(p) === false){
            p++;
        }
    return p;
};

这个函数可以工作，但是对于大数字它会崩溃，例如它在输入 (6310545154, 3) 时崩溃。顺便说一下 6310545154 的素次幂分解为 2 * 3155272577

所以我写了另一个函数，它首先只列出一个数的质因数:

var getFactors = function(n){
    var factors = [];
    var k = n;
    var p = 2;
    while(isPrime(k) === false && k !== 1){
        while(k % p !== 0 || isPrime(p) === false){
            p = p+1;
        }
        while(k % p === 0){
            k = k/p;
        }
        factors.push(p);
    }
    if(isPrime(k) === true){
        factors.push(k);
        return factors;
    }
    if(k === 1){
        return factors; 
    }
};

现在我对 findFirst 的第二次尝试是:

var findFirst = function(n,q){
    var array = getFactors(n);
    var p = 0;
    for(i = 0; i < array.length; i++){
        if(array[i] >= q && p === 0){
            p = array[i];
        }
    }
    return p;
};

这个很好用。它不会在上面那个大数字上崩溃并立即计算结果。谁能明白为什么会这样？看起来我最初尝试中的“while”循环与 getFactors 函数中的“while”循环之一非常相似。第二次尝试看起来要复杂得多。

Answer 1

第二个程序返回得很快，因为你的数字只有一个大质因数；一旦找到(所有)小质因数，它就会迅速退出循环。第一个程序必须从 3 一直数到 3155272577，然后才能发现它是一个因数。在 2147483647 之后，它必须从整数运算切换到浮点运算，这使得它更慢。

注意

var isPrime = function(n) {
    ...
};

是创建函数的一种不寻常的方式；通常你会写

function isPrime(n) {
    ...
}