时间戳

首页 > 解决方案 > How can I optimize my code to print amicable numbers?

python - How can I optimize my code to print amicable numbers?

问题描述

I have tried this following code and it takes a lot of time when I set lower = 0 and upper = 10000

def sumPdivisors(n):
  '''This function returns the sum of proper divisors of a number'''
  lst = []
  for i in range(1,n//2+1):
    if n%i == 0:
      lst.append(i)
  return(sum(lst))

lower = int(input("Enter the lower value of range: "))
upper = int(input("Enter the upper value of range: "))

lst = []

for i in range(lower, upper+1):
    if i == 0:
      continue
    else:
      for j in range(i, upper):
        if i!=j and sumPdivisors(i) == j and sumPdivisors(j) == i:
          lst.append((i,j))
          break

print(lst)

标签： pythonoptimization

解决方案

您可以在这里做两件事。

记忆

这个网站[link]上的其他地方已经有一个很好的解释，但这里是它与您的问题的相关性：

  • sumPdivisors在代码片段底部的 for 循环中非常频繁地调用。对于非常大的输入n，运行需要很长时间。

  • sumPdivisorsn多次调用相同的输入。

  • 您可以通过以某种方式保存调用sumPdivisors不同输入的结果来加快速度，例如在sumPdivisors使用相应整数调用时将整数映射到结果输出的字典中。这就是记忆化的一种。您正在预先计算可能的输出sumPdivisors并将它们存储起来以备后用。阅读链接以获得更深入的解释。

不要将 sumPdivisors 中的数字添加到列表中

您可以在迭代时添加这些数字，而不是将它们附加到列表中，然后将它们相加。此更改不会像在您的代码中添加 memoization 那样产生很大的影响。

推荐阅读