2

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

4

5 回答 5

3

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

注意

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

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

function isPrime(n) {
    ...
}
于 2012-09-01T23:17:17.043 回答
0

你有很多错误，在代码中 - 例如，这种方式i是全局变量

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

你想做的是

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

然后稍后

factors[i] = k;

哪里i没有定义等等。

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

于 2012-09-01T23:17:00.760 回答
0

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

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

阅读更多关于这篇文章。

编辑：虽然可能不是大数字的最佳选择。更像是一个快速的解决方案。

于 2012-09-01T23:29:11.483 回答
0

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

请记住，浏览器无法确定脚本是否会在不运行脚本的情况下完成——这被称为停止问题，对于图灵完备的编程语言来说，它是无法解决的。浏览器杀死脚本的提议是基于猜测，无论所讨论的脚本是什么，这都是正确的。

于 2012-09-01T23:37:59.493 回答
0

第二次尝试从不执行p = p+1;，实际上while在这getFactors部分只执行了 2 次：

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

与第一次尝试不同，第一次尝试必须测试p从 '3' 到 第一次尝试3155272577的素数和因子的每个数量n：

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

为什么？
第二次尝试以 and 开始， 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到3155272577终止外部while(isPrime(k) === false ...

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

ref: Eratosthenes Sieve - 维基百科

于 2014-05-09T23:12:21.780 回答