同一件事情的兩個函數，一個崩潰，另一個不崩潰，爲什麼？

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