如何查找無符號長整數的所有素數因子？

我有一個任務，以找到一個數字的所有素因子...如何查找無符號長整數的所有素數因子？

我需要寫一個函數，它需要一個數字，並告訴我所有的數字的主要因素。例如：

N = 350質因數：2 5 5 7

（I傳遞給函數的數爲0〜18446744073709551615的範圍 - 的最大數目是，適合在一個最大數64位無符號長整數。）

2010-11-22 david

你的想法是什麼？你有什麼嘗試？你卡在哪裏？這不是一個讓你的任務完成的網站，你需要告訴我們你已經做出了努力，然後你可以得到棘手的問題。作爲一個起點，請參閱維基百科：http://en.wikipedia.org/wiki/Integer_factorization – 2010-11-22 10:16:48

http://stackoverflow.com/questions/2267146/what-is-the-fastest-factorization-algorithm – joni 2010-11-22 10:18:42

這是一個難題，也是所有量子計算機研究的主要原因之一。看看Shor's Algorithm。沒有優化的簡單蠻力就需要1000年的時間，儘管在這種特殊情況下（64位整數），你應該能夠將運行時間縮短到幾分鐘。

假設你有一個微不足道的情況（至多）一個大素數因子，你可以通過做一些事情來加速顯着，比如從2開始計算並嘗試每個數字（如果它有效，則多次; 12將是2，2 ，例如3）。找到一個因子後，按照該因子減少目標數量，並測試新目標是否爲素數。

爲了進一步提高速度，您可以在多個線程中進行處理，每個線程負責一系列除數。您可以在一個或多個線程上運行素數測試人員，爲測試線程提供素數，以便您只嘗試按素數進行分配。

如果您認爲提供價值的人嘗試變得微不足道，您甚至可以從範圍的頂部搜索，儘管質數密度在低端的密度更高，但這可能不會幫幫我。

要記住的最重要的事情是X的最大可能因子除了X本身外還是X的平方根。每次找到一個因子時，最大可能的剩餘因子顯着減少。

來源

2010-11-22 14:24:38 Jonathan

不錯的使用trickome 。 – 2010-11-22 15:07:16

從2開始並繼續工作應該會更好，因爲素數的密度在低端附近更大，所以您有更好的機會在那裏找到主要因素。另外，每當你發現一個主要因素時，你就會把它分解成你所考慮的數字，這意味着你的上限變得更小。 – nategoose 2010-11-23 00:59:25

@nategoose好點。我會更新我的答案以反映。 – Jonathan 2010-11-23 13:41:26

如何查找無符號長整數的所有素數因子？

回答

相關問題