质因数分解算法

Question

我正在尝试编写一个函数，以找到给定数字的质因数分解。它不需要快速或高效，只需正常工作。

这是我的想法：

• 选择一个数字和一个起始点（将为2）。
• 如果该数字可被2整除，则将计数器加1并将该数字除以2。
• 当该数字不能被2整除时，将起始点更改为3。
• 重复进行以上步骤。

这是我的代码：

def ffs(num):

factors={}

n=2

while n<num:

    while num%n==0:

        num=num/n

        if n in factors:
            factors[n]+=1
        else:
            factors[n]=1


    n+=1

return factors

我早期遇到了一些问题。当我尝试计算 ffs(6) 时，我应该得到 {2:1,3:1}，但实际上我只得到了 {2:1}。请问有人能帮忙指出我的错误吗？

- user3600497

Answer 1

所以，你的算法看起来很好，除了你没有适当地讨论终止条件。实际上，它应该是当num == 1时。因此...

def ffs(num):
    factors = {}
    n = 2

    while num != 1:
        while num % n == 0:
            num /= n
            if n in factors:
                factors[n] += 1
            else:
                factors[n] = 1
        n += 1

    return factors

print ffs(6)

我们还可以使用collections.defaultdict来简化代码：

我们还可以使用collections.defaultdict，来简化代码：

from collections import defaultdict

def ffs(num):
    factors = defaultdict(lambda: 0)
    n = 2

    while num != 1:
        while num % n == 0:
            factors[n] += 1
            num /= n
        n += 1

    return dict(factors)

print ffs(6)

这两个代码块都会输出：

{2: 1, 3: 1}

- Bill Lynch

---

谢谢！这真的很有帮助。 - user3600497