divisor function 是自然数的除数之和。
做了一点研究,我发现 this 是一个非常好的方法,如果你想找到给定自然数 N 的除数函数,所以我尝试用 Python 编写它:
def divisor_function(n):
"Returns the sum of divisors of n"
checked = [False]*100000
factors = prime_factors(n)
sum_of_divisors = 1 # It's = 1 because it will be the result of a product
for x in factors:
if checked[x]:
continue
else:
count = factors.count(x)
tmp = (x**(count+1)-1)//(x-1)
sum_of_divisors*=tmp
checked[x]=True
return sum_of_divisors
它工作得很好,但我确信它可以改进(例如:我用
100000
元素创建了一个列表,但我没有使用其中的大部分)。您将如何改进/实现它?
附言这是
prime_factors
:def prime_factors(n):
"Returns all the prime factors of a positive integer"
factors = []
d = 2
while (n > 1):
while (n%d==0):
factors.append(d)
n /= d
d = d + 1
if (d*d>n):
if (n>1): factors.append(int(n));
break;
return factors
最佳答案
在计算除数之和时,您需要以 p1k1 p2k2 ... 的形式对 n 进行因式分解——也就是说,您需要因式分解中每个素数的指数。目前,您通过计算素因数的平面列表,然后调用 count
来计算指数。这是浪费时间,因为您可以轻松地以您首先需要的格式生成质因数分解,如下所示:
def factorization(n):
"""
Generate the prime factorization of n in the form of pairs (p, k)
where the prime p appears k times in the factorization.
>>> list(factorization(1))
[]
>>> list(factorization(24))
[(2, 3), (3, 1)]
>>> list(factorization(1001))
[(7, 1), (11, 1), (13, 1)]
"""
p = 1
while p * p < n:
p += 1
k = 0
while n % p == 0:
k += 1
n //= p
if k:
yield p, k
if n != 1:
yield n, 1
上面代码的注意事项:
append
)并返回它。在 Python 中,这种转换几乎总是一种改进,因为它允许您在元素生成时一个一个地使用它们,而不必将整个序列存储在内存中。 现在计算除数之和真的很简单:不需要存储检查因子的集合或计算每个因子出现的次数。实际上,您只需一行即可完成:
from operator import mul
def sum_of_divisors(n):
"""
Return the sum of divisors of n.
>>> sum_of_divisors(1)
1
>>> sum_of_divisors(33550336) // 2
33550336
"""
return reduce(mul, ((p**(k+1)-1) // (p-1) for p, k in factorization(n)), 1)
关于python - 你将如何实现除数函数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14359936/