你的算法是试除法，它的时间复杂度为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以及其他各种更强大的分解更大整数的方法。在