同一件事情的两个函数，一个崩溃，另一个不崩溃，为什么？

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) { 
    ... 
} 

Answer 2

你有一大堆的bug，在代码 - 例如，这种方式i是全局变量

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

你想要做什么是

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

再后来

factors[i] = k; 

其中i未定义等。

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

Answer 3

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

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

了解更多关于this post。

编辑：虽然可能不是最佳数量。更像是一个快速解决方案。

Answer 4

这并不直接解决这个问题，但我认为需要强调的是，无响应的标签与碰撞不同。无响应仅表示该页面在很长一段时间内一直在执行JavaScript。

请记住，浏览器无法确切知道脚本是否会在不运行脚本的情况下完成 - 这就是所谓的停止问题，以及图灵完整的编程语言，这是不可解的。浏览器提供的杀死脚本的提议基于猜测，无论问题是什么脚本，情况都是如此。

Answer 5

第二次尝试从未执行p = p+1;而事实上在这getFactors部分执行整个while只有2个：

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

不像必须从“3”测试p每隔数3155272577的第一次尝试素性和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到3155272577终止外while(isPrime(k) === false ...

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

裁判：Eratosthenes Sieve - Wikipedia