Python 代码卡在 Iterating 中，尽管它找到了解决方案

Question

我正在尝试编写一个 python 代码来查找任何给定数字的质因数

def pf(n):
    for i in range(2,n):
        if n%i==0: #find the factors
            for j in range(2,i): #check if the factor is prime
                if i%j==0:
                    break
            else: #find the prime ones
                print(i)

我的问题是这段代码对于小数字工作正常但是对于大数字我必须中断执行
例如:

pf(600851475143)
71
839
1471
6857
Traceback (most recent call last):
  File "<pyshell#11>", line 1, in <module>
    pf(600851475143)
  File "<pyshell#1>", line 2, in pf
    for i in range(2,n):
KeyboardInterrupt  

在不到一秒的时间内就找到了这个大数的质因数，所以我的问题是如何调整此代码以在使用 找到因数后停止不必要的迭代for 不是 while 循环

Answer 1

您可以通过将 n 除以每个迭代步骤中获得的值来加快速度。这样你就减少了你迭代的次数。我会实现这样的事情(还不确定这是否是最佳的并且导致最少的操作数):

from math import sqrt

def pf(n):
    if n == 1: 
        return
    if n % 2 == 0:
        print(2)
        pf(n/2)
        return
    for i in range(3, int(sqrt(n))+1, 2):
        if n % i == 0:
            for j in range(3, int(sqrt(i))+1, 2):
                if i % j == 0:
                    break
            else:
                print(i)
                pf(n/i)
                return
    print(n)

请注意，如果使用循环直到数的根的改进，我们将忽略数本身是质数的情况。但是，如果该函数不产生任何质因数，则可以假设输入本身就是质数。

return 语句在递归调用后停止主循环(和函数)。因此，每次调用该函数只会产生一个值，并且会根据该数字除以找到的素数的结果调用该函数。

如果您用所有质数创建一个集合并检查该值是否在此集合中，您将赢得一些时间，而不是循环遍历所有值。

与 non-recursive solution by jonrsharpe 相比这个速度几乎是原来的四倍:

>>> print timeit.timeit("pf(600851475143)", setup="from __main__ import pf", number=1)
71
839
1471
6857
0.00985789299011
>>> print timeit.timeit("pf2(600851475143)", setup="from __main__ import pf2", number=1)
71
839
1471
6857
0.0450129508972

实现受到range()的溢出限制，导致输入值(600851475143**2)+1溢出。有关 range 最大大小的更多详细信息，请参阅以下问题:Python: Range() maximum size; dynamic or static?

此解决方案的一个可能问题是达到了最大递归深度。有关该问题的更多详细信息，请访问此问题:Maximum recursion depth