python 素数分解的递归解法

Question

我是 python 的新手，我真的很难理解递归。我写了一个函数，它接受一个整数和 returns 一个包含素因数分解中所有数字的列表。

这是我反复写的：

def primeFac(n):
    lst=[]
    c=2
    while c<=n:
        if n%c==0:
            n//=c
            lst.append(c)
        else:
            c+=1
    return lst

哪个returns:

>>> primeFac(5)
[5]
>>> primeFac(72)
[2, 2, 2, 3, 3]

如何递归执行此操作？这似乎没有必要，但我确实需要为期末考试学习这样做。

这是我到目前为止写的：

def primeFac(n):
    lst = []
    c = 2
    if n<=c:
        lst.append(n)
    else:
        while n%c!=0:
            c+=1
        if n==c:
            lst.append(n)
        else:
            lst.append(c)
            lst.append(primeFac(n//c))
        return lst

我得到：

>>> primeFac(5)
[5]
>>> primeFac(72)
[2, [2, [2, [3, [3]]]]]

Answer 1

除此之外，您的代码还不错：

    lst.append(primeFac(n//c))
return lst

您附加 return 和 return 一个列表，因此您将在您使用的 "normal" 迭代中将一个列表附加到您的列表：

 lst.append(c)

所以你只是附加了值。

您可以这样做来连接列表：

lst = lst + primeFac(n//c))

python 素数分解的递归解法

python recursive solution for prime factorization

python

recursion

prime-factoring