Python递归程序以素数分解

小编典典

Python递归程序以素数分解

algorithm

我编写了以下程序来素数分解：

import math
def prime_factorize(x,li=[]):
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
        if not x%i:
            li.append(i)
            break
    else:                      #This else belongs to for
        li.append(x)
        print li               #First print statement; This is what is returned
        return li
    prime_factorize(x/i,li)

if __name__=='__main__':
    print prime_factorize(300)   #Second print statement, WTF. why is this None

以下是我得到的输出：

 [2, 2, 3, 5, 5]
 None

而且，返回值已正确打印，之后的返回值似乎一直都未打印。我想念什么？

另外，我该如何改善程序（继续使用递归）

阅读 461

2020-07-28

共1个答案

小编典典

您的prime_factorize函数在递归情况下没有return语句-您要在其最后一行调用“ return prime_factorize（x /
i，li）”。尝试使用质数（因此不需要递归调用）以查看在这种情况下它是否有效。

另外，您可能想要使签名类似：

def prime_factorize(x,li=None):
    if li is None: li = []

否则，在两次或更多次调用时会得到错误的结果：

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]

2020-07-28