除数関数は、自然数の約数の合計です。
少し調べてみると、与えられた自然数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
が、ほとんどの要素を使用していません)。
どのように改善/実装しますか?
PSこれは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