TA貢獻1817條經驗 獲得超14個贊
實際上，有幾種更有效的方法可以找到大數字的因子（對于較小的因子，試驗分工合理地工作得很好）。
如果輸入數字具有非常接近其平方根的兩個因子，則一種非?？斓姆椒ǚQ為費馬因子分解。它利用身份N =（a + b）（a - b）= a ^ 2 - b ^ 2，易于理解和實現。不幸的是，它一般不是很快。
最常見的分解數字長達100位的方法是Quadratic篩。作為獎勵，部分算法可以通過并行處理輕松完成。
我聽說的另一種算法是Pollard的Rho算法。它一般不如Quadratic Sieve效率高，但似乎更容易實現。
一旦你決定如何將一個數字分成兩個因子，這里是我能想到的最快的算法，找到一個數字的最大素數因子：
創建一個最初存儲號碼本身的優先級隊列。每次迭代，您從隊列中刪除最高的數字，并嘗試將其分成兩個因子（當然，不允許1成為這些因素之一）。如果此步驟失敗，則數字為素數，您就有了答案！否則，將兩個因子添加到隊列中并重復。
TA貢獻1877條經驗 獲得超1個贊
這是我所知道的最好的算法（在Python中）
def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 return factors pfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list
上述方法在O(n)最壞的情況下運行（當輸入是素數時）。
編輯：
以下是O(sqrt(n))評論中建議的版本。這是代碼，再一次。
def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 if d*d > n: if n > 1: factors.append(n) break return factors pfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list
TA貢獻1780條經驗 獲得超1個贊
我的答案是基于Triptych的，但在其上有很大的改進。它基于超過2和3的事實，所有素數都是6n-1或6n + 1的形式。
var largestPrimeFactor;if(n mod 2 == 0){
largestPrimeFactor = 2;
n = n / 2 while(n mod 2 == 0);}if(n mod 3 == 0){
largestPrimeFactor = 3;
n = n / 3 while(n mod 3 == 0);}multOfSix = 6;while(multOfSix - 1 <= n){
if(n mod (multOfSix - 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
if(n mod (multOfSix + 1) == 0)
{
largestPrimeFactor = multOfSix + 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
multOfSix += 6;}我最近寫了一篇博客文章，解釋了這個算法的工作原理
我敢說，一種不需要進行素數測試（并且沒有篩子構造）的方法比使用那些方法的方法運行得更快。如果是這種情況，這可能是這里最快的算法。
舉報