我刚刚完成了第三个项目欧拉问题,该问题要求您找到给定数字的最大质因数。我创建了一个函数,该函数返回一个数字的所有质因数列表。
例如,如果您输入 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 并不会使乘积大于目标数。
我觉得这可能是解决问题的完全错误的方法,但我坚持要改变什么。
请您参考如下方法:
您应该使用模运算符 %。假设您有一个数字 270。因此,您将 270 除以 3,直到它被“剥离”掉 3,即。没有 3 的因数了。
- 270/3=90
- 90/3=30
- 30/3=10
- 10 不能被 3 整除。
所以,270=10 * 33
使用质因数函数:
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
注意事项
不要将 float 用于数论问题。首先,模运算符对它们不起作用。其次,您永远不知道什么时候您会成为精度不准确的受害者。示例:
0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0的计算结果为False。如果您需要检查整除性,请使用 % .您的代码失败的原因是正确的。对于 18,
prime_factors(18)=[2,3].因为 24 < 18 < 25。您的函数报告 2 的 18 次方是 4,这是错误的。
