Sum of divisors
Sum of divisors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Given a positive integer, sum its positive divisors.
- Task
Show the result for the first 100 positive integers.
Python
Using prime factorization
<lang Python>def factorize(n):
assert(isinstance(n, int)) if n < 0: n = -n if n < 2: return k = 0 while 0 == n%2: k += 1 n //= 2 if 0 < k: yield (2,k) p = 3 while p*p <= n: k = 0 while 0 == n%p: k += 1 n //= p if 0 < k: yield (p,k) p += 2 if 1 < n: yield (n,1)
def sum_of_divisors(n):
assert(n != 0) ans = 1 for (p,k) in factorize(n): ans *= (pow(p,k+1) - 1)//(p-1) return ans
if __name__ == "__main__":
print([sum_of_divisors(n) for n in range(1,101)])</lang>
Finding divisors efficiently
<lang Python>def sum_of_divisors(n):
assert(isinstance(n, int) and 0 < n) ans, i, j = 0, 1, 1 while i*i <= n: if 0 == n%i: ans += i j = n//i if j != i: ans += j i += 1 return ans
if __name__ == "__main__":
print([sum_of_divisors(n) for n in range(1,101)])</lang>
- Output:
[1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144, 72, 195, 74, 114, 124, 140, 96, 168, 80, 186, 121, 126, 84, 224, 108, 132, 120, 180, 90, 234, 112, 168, 128, 144, 120, 252, 98, 171, 156, 217]