素数分解算法

Question

我试图写一个函数来求给定数的素数因式分解。它不需要快，也不需要高效，它只需要工作。在

我的想法是：

• 选择一个数字和一个起点（2）。在
• 如果这个数可以被2整除，则在计数器上加一，然后除以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}。有人能发现我的错误吗？在

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，稍微简化代码：

^{pr2}$

这两者都将输出：

{2: 1, 3: 1}