python - 如何更有效地求平方和？

Question

家庭作业涉及创建一个函数来检查一个数字是否是两个平方和。我有一个函数可以工作，但这是一种非常粗暴的方法，并且较大的整数需要更长的时间才能运行它。我能做些什么来让它更有效地处理更大的数字吗？需要注意的是，该函数必须返回最大元组，因此例如给定整数 50 而不是返回 (5,5) 的函数，我会喜欢它返回 (7,1) 函数如下:

def sum_of_squares(n) : 
  i = 1 

  while i * i <= n : 
      j = 1

      while(j * j <= n) : 

          while (i * i + j * j == n) : 

              return (j,i)

          j = j + 1
      i = i + 1

Answer 1

有一种基于内存的非常优雅的方法，因此几乎是动态编程。时间复杂度为O(sqrt(n))。

from math import sqrt, ceil
def sum_square(n): 

    s = set()
    results = []
    for i in range(ceil(sqrt(n))):

        i_square = i * i
        s.add(i_square)  # remember square value 

        if (n - i_square) in s:
            results.append((i, sqrt(n - i_square)))
            #print(f"{sqrt(n - i_square)}^2 + {i}^2") 
            #return True
    #return False
    return results[-1] if results else None

n = 169
print(sum_square(n))