使用JavaScript檢查素數號碼

我正在執行第三個項目euler問題。到目前爲止，我已經想出瞭如何解決發現600851475143的最大素因子的問題。使用JavaScript檢查素數號碼

我已經寫了一小段代碼，可以將數字的所有素數因子放入數組中。我遇到的問題是數字可能太大而無法計算。我已經使用了其他大數字（不像這個數字那麼大），並且它們工作得很好，但是這只是將頁面凍結起來，就像無限循環一樣。這裏是代碼：

var primes = []; 
function factor (largestNumber) { 
    var a = largestNumber; 
    var b = 2; 
    while (b < largestNumber) { 
     if (a % b == 0) { 
      a /= b; 
      primes.push(b); 
      b = 2; 

     } else { 
      b++; 
     } 
    } 
} 

factor(600851475143); 
console.log(primes);

來源

2014-02-21 Vodka_Tonic

你至少應該知道，你只需要測試多達開方（NUM），你可以在實際上更新（更低）的約束循環的，當你發現一個因素。 – nhahtdh

@LowerClassOverflowian：問題並不在於尋找素數（儘管它有幫助）。這是一個分解問題。 – nhahtdh

你的算法不是最優的。

function factor(largestNumber) { 
    var primes = [];       // using local value 
    var a = largestNumber; 
    var b = 2; 
    while (b <= Math.floor(Math.sqrt(a))) { // we do not need to check whole number 
               // over and over again. 
               // We could check to a only 
               // or even to sqrt(a) only 
     if (a % b == 0) { 
      a /= b; 
      primes.push(b); 
              // there is no reason to reset value 
     } else { 
      b++; 
     } 
    } 
    primes.push(a);       // rest number would be always prime 
    return primes; 
} 

console.log(factor(600851475143));

來源

2014-02-21 03:58:32 sectus

這可能是一種有用的方法，將最大的主要因素分爲3部分。

最大切割民成2密切NUM如40 => 5 * 8
獲取更大的NUM（8）並找出所有質NUM比它小。存儲到陣列中。
使用循環來獲得最大的素數因子。

就是這樣，今晚我會試試。如果我做到了，我會添加jsfiddle addr。：）

來源

2014-02-21 03:58:19

使用JavaScript檢查素數號碼

回答

相關問題