素数分解-列表

Question

我正在尝试实现一个函数primeFac()，该函数将正整数作为输入n并返回包含的素数分解中所有数字的列表n。

我已经走了这么远，但我认为最好在这里使用递归，不确定如何在这里创建递归代码，基本情况是什么？首先。

我的代码：

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?

Answer 1

一个简单的审判部门：

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

具有O(sqrt(n))复杂性（最坏的情况）。您可以通过特殊情况2并仅在奇数上循环d（或特殊情况下将更多小质数并在可能的除数上循环）来轻松改进它。