更新字典的简单递归程序冻结计算机

Question

我的简单递归程序更新了一本字典，使整个计算机冻结了很长一段时间。我写了一个脚本来查找所有的基本因子及其计数，并将它们放入字典

例如：如果N=p^Nxq^m

那么字典应该是：{ 1:1 , p:n , q:m }

我的代码适用于较小的数字，但对于较大的数字，如54365765878，它会使计算机长时间冻结，任务管理器显示我的脚本使用了2 Gb中的1.4 Gb内存

这是我的代码：

M=int(input('Enter M\n'))

M_fac={1:1}

def fac_rec(m):
    global M_fac
    for d in [k for k in range(2,int(m//2)+1)]+[int(m)]:
        if m%d==0 and d!=1:
            if d in M_fac:
                M_fac[d]+=1
            else:
                M_fac[d]=1
            fac_rec(m/d)
            break

fac_rec(M)

print(M_fac)

我的代码出了什么问题，如何修复

Answer 1

这是一个可怕的递归用法

现在，这已经不成问题了，我相信您的代码的问题在于这一行：

for d in [k for k in range(2,int(m//2)+1)]+[int(m)]:

我们不是简单地循环这个（可能很大的）数字范围，而是创建必须存储在内存中的实际列表(我知道这样做的原因是，如果m是素数，那么附加项是必要的。但让我们重新设计代码以避免创建此列表（以及其他调整）：

from collections import defaultdict

M = int(input('Enter M: '))

M_fac = defaultdict(int, {1: 1})

def fac_rec(m):
    global M_fac

    for d in range(2, m // 2 + 1):
        if m % d == 0:
            M_fac[d] += 1

            fac_rec(m // d)
            return

    M_fac[m] += 1  # m is prime!

fac_rec(M)

print(dict(M_fac))

输出

> python3 test.py
Enter M: 54365765878
{1: 1, 2: 1, 29: 1, 89: 1, 163: 1, 64613: 1}
>

验证

> dc
1 2 * 29 * 89 * 163 * 64613 * p
54365765878
>