改進快速分解代碼？

Question

我想讓這段代碼更快。它返回一個長整數的所有因素（素數）。如果longNumber是特定的，那麼顯然需要執行幾分鐘。

int div = 2; 
String factors = ""; 

while (longNumer != 1) 
{ 
    if (longNumer % div == 0) 
    { 
     longNumer /= div; 
     factors += div + " "; 
    } 
    else { div++; } 
} 

//longNumber = 10, gives: 2 5. 
//longNumber = 150, gives: 3 5 7. 
//longNumber = 10523, gives: 17 619. 

它需要太長的數字，如「7544222046562688368」，並且它不好，你會建議什麼？

Answer 1

您可以使用以下步驟來代替 -

找到所有質數< =開方（longNumber）。並將它們保存在一個數組中 - primes。
2.現在逐漸使用數組的元素 - primes作爲除數來查找該因子。

Answer 2

對於大的號碼，你可以使用Sieve of Eratosthenes algorithm先找到素數最多的sqrt（N），然後你必須檢查是否這些素數因素

Answer 3

暗示埃拉托色尼的篩的答案將不爲你描述的數字做很多事情。對於64位數sqrt(2^64) = 2^32，這仍然很多。

對於那些，最好的賭注Pollard's Rho algorithm或更復雜的整數分解方法列出here：

代數組因數分解算法，其中有波拉德是P＆ - 1種算法，Williams的P + 1算法，和倫斯特拉橢圓曲線分解

Fermat的分解方法

歐拉因式分解法

特殊數域篩

Answer 4

一個好辦法因素的64位整數，這是既簡單編程，並在實踐中合理有效，綜合審判庭與波拉德的RHO算法。這裏是僞代碼：

function factors(n) 
    wheel := [1,2,2,4,2,4,2,4,6,2,6] 
    w, f, fs := 0, 2, [] 
    while f*f <= n and f < 10000 
     while n % f == 0 
      fs, n := f :: fs, n/f 
     f, w := f + wheel[w], w+1 
     if w = 11 then w = 3 
    if n == 1 return fs 
    h, t, g, c := 1, 1, 1, 1 
    while not isPrime(n) 
     repeat 
      h := (h*h+c) % n # the hare runs 
      h := (h*h+c) % n # twice as fast 
      t := (t*t+c) % n # as the tortoise 
      g := gcd(t-h, n) 
     while g == 1 
     if isPrime(g) 
      while n % g == 0 
       fs, n := g :: fs, n/g 
     h, t, g, c := 1, 1, 1, c+1 
    return n :: fs 

這使用2,3,5輪審判分爲10000然後簡單的實施rho算法;它應該在幾毫秒內將您的樣本數量設爲7544222046562688368 = 2 * 2 * 2 * 2 * 7 * 7 * 14618561 * 658254407。改進是可能的，但這應該足以讓你開始。

Answer 5

在實施其中一種分解算法比試劃更快之前，一個容易糾正的錯誤是避免在最後一塊的sqrt之後進行試劃分。

while (longNumber != 1) { 
    if (longNumber % div == 0) { 
     longNumber /= div; 
     factors += div + " "; 
    } 
    else { 
     if (div*div>longNumber) { 
      if (longNumber > 1) 
       factors += longNumber + " "; 
      break; // leave the while loop. 
     } 
     div++; 
    } 
} 

設兩個最大的素因子是P1和P2。在你的版本中，你可以做一些關於c P1的操作。在修改後的版本中，你可以做c Max（sqrt（P1），P2）。在7544222046562688368上，改進應該是45的因子。

另一個改進是更改div ++行。你不需要用大於2的偶數進行試劃，也不需要用大於3的3整除。避免這些因素可以使計算速度提高2倍以上，並且可以通過避免測試其他小素數的倍數來做得更好。但是，你不想花時間用小素數對div進行審判。相反，你要跟蹤當前的和允許的餘數mod 2 * 3 * 5 * 7。這被稱爲使用小素數的輪子。

一些其他的答案已經討論過使用篩子來找到所有小素數，然後僅通過這些試算來進行試用。如果你只考慮一個數字，這不會起作用，因爲篩選素數需要很長的時間。生成sqrt（n）的素數列表大約需要c sqrt（n）loglog n操作，而對sqrt（n）進行的所有事情的劃分都需要大約c sqrt（n）的操作。如果您需要計算許多大數，則執行一次篩選並存儲結果可能會有所幫助。