python - 如何计算给定数字的素因数指数？

Question

我刚刚完成了第三个项目欧拉问题，该问题要求您找到给定数字的最大素因数。我创建了一个函数，它返回一个数字的所有素因数的列表。

例如，如果您输入 100，则会返回 [2.0, 5.0]

我现在想尝试制作一个程序，该程序返回一个列表，其中素数因子出现的次数与其指数相同。

例如，输入 100 将返回 [2.0, 2.0, 5.0, 5.0](因为 100 是 2^2 * 5*2)。

我编写了一个函数，如果放入包含素因数的列表和包含指数的列表，该函数可以正确执行此操作。问题是我用来获取指数列表的函数是错误的。

我编写的代码对于某些数字(18、36、50、54...)失败。

我对编程相当陌生，因此如果有人可以帮助我，我将非常感激。

def p_fctr_exp(n):
    """Prime factorises n and gives the exponents of each factor"""
    l1 = prime_factors(n) #Initialisation of variables and lists ('prime_factors() ) is just the function I made which gives a list of the prime factors
    p = 1
    exp=[]
    result=[]
    for x in l1:    #This multiplies the prime factors together just once
        x = float(x)
        p = (p * x)
    for x in range(0,len(l1)):  
        """Loop which cycles through factors from smallest first and multiplies 
    the total by the factor until the point where one more would make it bigger
    than the target number. The number of cycles required is stored in the 
    list 'exp'""" 
        a=1
        while p<n:
            p = p*float(l1[x])
            a+=1
        if p == n:
            exp.append(a)
        elif x < len(l1)-1:
            exp.append(a-1)
    return exp

我认为问题出现在 while 循环中，因为它的工作原理是将乘积 p 乘以最低的素因数，直到它变得太大，然后向上移动到下一个素因数。问题是，如果说正确的指数应该是 2，但将其增加到 3 并不会使乘积大于目标数字。

我有一种感觉，这可能是解决问题的完全错误的方法，但我坚持要改变什么。

Answer 1

您应该使用模运算符 %。假设你有一个数字 270。因此，你将 270 除以 3，直到它被“剥离”掉 3，即。没有剩下 3 的因数了。

• 270/3=90
• 90/3=30
• 30/3=10
• 10 不能被 3 整除。

所以，270=10 * 3³

使用素因数函数:

def p_fctr_exp(n):
    primes = prime_factors(n)
    exp=[]

    for p in primes:
        e=0
            while (n%p==0):
            n=n//p       # since p still divides n,
            e+=1         # we divide n by p and increase the exponent
        exp.append(e)
    return exp

注释

1. 不要在数论问题中使用 float 。首先，模运算符对它们不起作用。其次，你永远不知道什么时候你会成为精度不准确的受害者。示例:0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0 计算结果为 False。 如果您需要检查整除性，请使用 % .

2. 您的代码失败的原因是正确的。对于 18，prime_factors(18)=[2,3]. 自 2⁴ < 18 < 2⁵ 开始。您的函数报告 2 的 18 次幂是 4，这是错误的。