找到數字的所有因素的最有效方法？

免責聲明：有這一個在如此相似的問題，但是他們都要麼根本不提算法的效率，或者是寫在不同的語言。請參閱this answer，其中談到關於python的效率，看看它是否有助於您回答我的問題。找到數字的所有因素的最有效方法？

所以我需要最快捷的方式找到所有的任何給定數量的帶有大量迅速工作的因素。我已經有幾次迭代的代碼可行，但需要很長時間才能處理超過6個字符的數字。

編輯：根據要求這裏是我的一些這樣的非有效的方式（錯誤檢查爲清楚起見，省略了）

真的很亂：

@IBAction func findFactorsButton(_ sender: AnyObject) { 
    if let _ = textField.text, !textField.text!.isEmpty { 
     counter = 1 
     factors = [] 
     repeat { 
      counter += 1 
      if Int(textField.text!)! % counter == 0 { 
       factors.append(String(counter)) 
      } else { 
       continue 
      } 
     } while counter != Int(textField.text!) 
     factors.removeLast() 
     outputLabel.text = factors.joined(separator: ", ") 

    } else { 
     outputLabel.text = "" 
    } 
}

較不凌亂的解決方案（遊樂場）：

func calculateFactors(n: Int) -> String { 
    var result: String = "" 
    for i in 1...n { 
     guard n % i == 0 else {continue} 
     result += i == 1 ? "1" : ", \(i)" 
    } 
    print(result) 
    return result 
}

來源

2017-08-01 Cobie Fisher

你能不能告訴我們這些迭代，在性能最好的，以最後上市？ – dfd

保理單號碼的有效性？還是很多？在後一種情況下，您可以預先計算素數列表。數字在多大範圍內？ –

這裏的https://codereview.stackexchange.com/a/166342/35991是一個應該比你的更快的實現。 –

大多數的Python方法的What is the most efficient way of finding all the factors of a number in Python?使用的事實，n 因素是成對出現的：如果i是一個因素則n/i是另一個因素。因此，測試給定數字的平方根的係數就足夠了。

以下是在夫特一個可能的實現：

func factors(of n: Int) -> [Int] { 
    precondition(n > 0, "n must be positive") 
    let sqrtn = Int(Double(n).squareRoot()) 
    var factors: [Int] = [] 
    factors.reserveCapacity(2 * sqrtn) 
    for i in 1...sqrtn { 
     if n % i == 0 { 
      factors.append(i) 
     } 
    } 
    var j = factors.count - 1 
    if factors[j] * factors[j] == n { 
     j -= 1 
    } 
    while j >= 0 { 
     factors.append(n/factors[j]) 
     j -= 1 
    } 
    return factors 
}

備註：

reserveCapacity用於避免陣列重新分配。
範圍1...sqrtn所有因素首先確定，然後 n/i以相反的順序所附的相應的因素，使得所有因素是遞增的順序。
必須特別注意，對於完美的方塊，sqrt(n)是沒有列出兩次。

對於最多8個小數位的數字，最多9999個試用個分部是必需的。例如（在1.2 GHz英特爾酷睿M5的MacBook，在發行模式下編譯）：

let start = Date() 
let f = factors(of: 99999999) 
print("Time:", Date().timeIntervalSince(start) * 1000, "ms") 
print("Factors:", f)

輸出：

 
Time: 0.227034091949463 ms 
Factors: [1, 3, 9, 11, 33, 73, 99, 101, 137, 219, 303, 411, 657, 803, 909, 1111, 1233, 1507, 2409, 3333, 4521, 7227, 7373, 9999, 10001, 13563, 13837, 22119, 30003, 41511, 66357, 81103, 90009, 110011, 124533, 152207, 243309, 330033, 456621, 729927, 990099, 1010101, 1369863, 3030303, 9090909, 11111111, 33333333, 99999999]

來源

2017-08-01 20:27:31

感謝您的回答Martin，它的工作方式比我以前的版本更高效 –

這一切都取決於你的號碼。這裏是一個很棒的summary：

「你的號碼有多大？決定使用方法：

小於2^16左右：查找表。

小於2^70左右： ~~Sieve of Atkin。這是更爲人熟知的 Sieve of Eratosthenes的優化版本。~~ 編輯：Richard Brent's modification Pollard's rho algorithm在這種情況下可能會更好。

小於10^50：Lenstra elliptic curve factorization

小於10^100：Quadratic Sieve

超過10^100：General Number Field Sieve

因此，一切都變得采摘算法和實現它們的問題在Swift中。既然你說你需要帶有「6個字符」的數字，這意味着他們大概在2^17左右。因此，該列表中的選項2：Atkin篩選或Pollard's rho的修改。在引用Q &

來源

2017-08-01 19:16:54 ColGraff

那麼你能分享一下swift中改進的Pollard Rho算法的實現嗎？ –

我沒有在Swift中的實現，你必須實現它或找到它。鏈接給出了一般算法，在Swift中編寫它應該相對容易。 – ColGraff

找到數字的所有因素的最有效方法？

回答

相關問題