你的算法是試除法，它的時間複雜度為O(sqrt(n))。您可以通過隻使用2和奇數作為試除數來改進您的算法，或者隻使用素數作為試除數更好，但是時間複雜性将保持為O(sqrt(n))。在
為了更快，你需要一個更好的算法。試試這個：def factor(n, c):
f = lambda(x): (x*x+c) % n
t, h, d = 2, 2, 1
while d == 1:
t = f(t); h = f(f(h)); d = gcd(t-h, n)
if d == n:
return factor(n, c+1)
return d
用你的号碼打電話，說
^{pr2}$
這實際上立即傳回(可能是複合)因子2090327。它使用了一種叫做rho算法的算法，由johnpollard在1975年發明。rho算法的時間複雜度為O(sqrt(sqrt(n))，比試除法快得多。在
還有許多其他的整數因式分解算法。對于您感興趣的20到35位數範圍内的數字，橢圓曲線算法非常适合。它應該在不超過幾秒鐘的時間内計算出這個大小的數字。特别是那些素數中的兩個素數，特别适合于這兩個素數的算法。在
如果您對使用質數程式設計感興趣，我在我的部落格上謙虛地推薦this essay。當你完成這些之後，我部落格上的其他條目将讨論橢圓曲線因式分解、SQUFOF以及其他各種更強大的分解更大整數的方法。在