如何讓我的代碼更慢（JavaScript） - 最大的素因子

我打算在Javascript中找到數字n的最大素數因子。但是，我認爲這個代碼是放慢速度或者可以排序的，但是我沒看到如何。這一點將顯示數組因子的最後一個元素，這將是最大的因素。任何人有關於如何縮短這一點的提示？問題是我的瀏覽器通知我該頁面花了很長時間來響應12位數字。我應該可能不使用數組？如何讓我的代碼更慢（JavaScript） - 最大的素因子

function biggest(n) { 
// Makes a list of primes smaller than n 
var primes = [2]; 
for (i=3; i < n ; i++) { 
    var j=0; 
    while (j<primes.length) 
    { var quotient = i/primes[j]; 
    if (quotient !== Math.floor(quotient)) 
      {var hasDivisor = false; 
      j++; 
      } 

     else 
      {var hasDivisor = true; 
      j=primes.length+1; 
      } 

    } 

    if (hasDivisor == false) 
     {primes.push(i);} 
} 


// Makes a list of factors 
var factors = []; 
for (i=0; i<primes.length; i++) { 
    var quotient = n/primes[i]; 

    if (quotient==Math.floor(quotient)) { 

     factors.push(primes[i]);} 
} 
    if (factors.length==0) { 
    factors.push(1); 
} 


    items.push("De biggest factor is "+ factors[factors.length-1] +"!"); 



}

來源

2015-02-05 wowlolbrommer

只需要循環直到n/2，並且您可以使用i + 2而不是i ++來循環遍歷奇數。 – 2015-02-05 18:07:45

感謝您的i + = 2提示，循環到n/2哪裏？第一部分代碼是找到素數，不一定是除n的素數。 – wowlolbrommer 2015-02-05 18:23:18

你只需要素數高達ñ平方根列表，因爲如果ň = p * q，一方或另一方p或Q的必須小於的平方根n（除非當n是一個完美的正方形）。而不是通過迭代所有可能的因子來計算素數，而使用Eratosthenes的篩子要快得多;在僞代碼：

function primes(n) 
    ps := [] 
    sieve := makeArray(2..n, True) 
    for p from 2 to n 
     when sieve[p] 
      append p to ps 
      for i from p*p to n step p 
       sieve[i] := False 
    return ps

來源

2015-02-05 20:11:16 user448810

啊，是的，不知道爲什麼我沒有考慮平方根。然而，這是篩選可能在JavaScript？ – wowlolbrommer 2015-02-06 20:47:00

@Wowlolbrommer：是的，當然篩選是可能的Javascript。但我會留給你翻譯。 – user448810 2015-02-07 00:36:46

做二維數組甚至存在於javascript中？ – wowlolbrommer 2015-02-07 23:52:49

如何讓我的代碼更慢（JavaScript） - 最大的素因子

回答

相關問題