同一事物的两个函数,一个崩溃,另一个不崩溃,为什么

Two functions for the same thing, one crashes and the other does not, why?

本文关键字:崩溃 一个 另一个 为什么 函数 两个      更新时间:2023-09-26

我想要一个名为findFirst的函数,它接受参数n和q,并返回小于或等于q的最小素数除以n。所以首先我写了一个函数,可以说一个数字是否是素数。

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"循环之一非常相似。第二次尝试看起来要复杂得多。

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

请注意,

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

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

function isPrime(n) {
    ...
}

你在代码中有很多错误 - 例如,这样i是全局变量

for(i=2; i < n; i++){

你想做的是

for(var i=2; i < n; i++){

然后后来

factors[i] = k;

未定义i的位置等等。

通过 jslint 或 jshint 运行代码,使其首先完全正确。

您可以使用正则表达式快速检查质数。

function isPrimeNumber(n) {
    return !/^1?$|^(11+?)'1+$/.test((new Array(++n)).join('1'));
}

阅读这篇文章的更多信息。

编辑:也许不是大数字的最佳选择。更像是一个快速的解决方案。

这并没有直接解决问题,但我认为重要的是要强调无响应的选项卡与崩溃不同。无响应仅意味着页面已经执行JavaScript很长时间了。

请记住,浏览器无法确定脚本是否会在不运行脚本的情况下完成 - 这称为停止问题,对于图灵完备编程语言,这是无法解决的。浏览器提供终止脚本是基于猜测,无论有问题的脚本是什么,这都是正确的。

第二次尝试永远不会执行p = p+1;,实际上在这个getFactors部分中只执行了整个while 2 倍:

   while(k % p !== 0 || isPrime(p) === false){
        p = p+1;
    }
与第一次尝试

不同,第一次尝试必须在第一次尝试中测试从"3"到3155272577的每个p数的素数和n因子:

    while(n % p !== 0 || isPrime(p) === false){
        p++;
    }

为什么?
第二次尝试从var p = 2;var k = n;开始,这意味着(k % p === 0)isPrime(p)都是true(当n=6310545154时(

while(isPrime(k) === false && k !== 1){
    while(k % p !== 0 || isPrime(p) === false){
        p = p+1;                                               /*  this is never executed for findFirst(6310545154, 3)  */
    }
    while(k % p === 0){
        k = k/p;
    }
    ...

然后k = k/p;立即将k降低到终止外部while(isPrime(k) === false ... 3155272577

要在第二次尝试中观察到相同的异常时间行为,请使用:
var factors = [2];var p = 3; .

参考: 埃拉托色尼筛 - 维基百科