Skip to content

Instantly share code, notes, and snippets.

@voith
Created November 5, 2019 16:40
Show Gist options
  • Save voith/c82b1adb7d567d76a83930ba16c557de to your computer and use it in GitHub Desktop.
Save voith/c82b1adb7d567d76a83930ba16c557de to your computer and use it in GitHub Desktop.
sum of all the amicable numbers under 10000
from math import sqrt
def _sum_of_proper_divisors(n, sum_of_proper_divisors):
_sum = 1
sqrt_n = int(sqrt(n))
for i in range(2, sqrt_n+1):
if n % i == 0:
_sum += i
if n // i != i:
_sum += n // i
sum_of_divsors_map[n] = _sum
def sum_of_proper_divisors(n, sum_of_proper_divisors):
if n not in sum_of_divsors_map:
_sum_of_proper_divisors(n, sum_of_proper_divisors)
return sum_of_divsors_map[n]
def calculate_sum_of_amicable_numbers(upper_limit):
_sum = 0
sum_of_divsors_map = dict()
for i in range(1, upper_limit + 1):
sum_of_div = sum_of_proper_divisors(
i,
sum_of_divsors_map
)
if (
sum_of_div > i and
sum_of_div <= upper_limit and
sum_of_div != i and
sum_of_proper_divisors(sum_of_div, sum_of_divsors_map) == i
):
_sum += (sum_of_div + i)
return _sum
if __name__ == '__main__':
print(
calculate_sum_of_amicable_numbers(10000)
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment