素數分解算法：如何使其更快？

Question

我有一個程序可以查找給定數字的主要因素。該算法以下述方式工作。

1）當n是2，打印2和整除n整除2.

2）步驟1之後，n必須是奇數。現在開始從i = 3到n的平方根的循環。當我劃分n時，打印i並將n除以i，將i遞增2並繼續。 3）如果n是一個素數並且大於2，那麼n將不會在上述兩個步驟中變爲1。所以如果它大於2，打印n。

有沒有辦法讓它更快？

Answer 1

您可以通過除質量而不是複合物來加快速度。如果它可以被複合物整除，那麼除以複合物的主要因子時，你就會發現它。例如，如果你已經確定它可以被3整除（並且正確地減少它），那麼沒有必要測試一個數字是否可以被9整除。另外，在你確定你測試的值是不可被它整除的情況下，我不會提前測試值（在你的情況下是兩倍，到下一個值）。

案例：27當你的測試值是3，你的算法將27 3得到9，然後立即增加測試值5.應當在3左直到你數除以不再是一個因素。