如何优化一个算法，将一个数分解为两个平方和？

Question

我有一个简单的数学算法。它只需要一个输入，然后找到i，j，这样i^2+j^2=输入，限制为j>；=i（这样它就不会打印它的对应项，例如，2^2+3^2==3^2+2^2，但我只需要后者作为j>；=i）

对于我的代码，我做了以下工作：我有2个For循环，第一个循环用于I，第二个循环用于j。获取I和j值，并测试I^2+j^2==输入，如果j>；=I。如果是，则打印并更新计数。在

问题是，对于大量的值，它需要很长的时间，因为它从1循环到2000循环两次，然后从1循环到2000循环。在

def some_mathfn(n):
    count = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if(i**2 + j**2 == n and j >= i):
                g = print(i, '^2 + ', j,'^2')
                count += 1
    return count

some_mathfn(2001)

Answer 1

你有一个O（n²）算法，没有明显的原因。很容易使这个O（n^1/2）。。。在

• 从1循环到n/2的平方根（对于变量i），因为当i大于sqrt(n/2)时，对于任何大于j的i*i + j*j将大于n。
  • （只计算n的平方根，因为
• 减去i的平方
• 取结果的平方根，找到最接近的整数调用j
• 检查你感兴趣的条件是否成立

最后两个步骤有效地只是检查n - i*i的平方根是否为整数，但在某些情况下（对于非常大的n值），找到最近的整数然后检查条件可能是一种更可靠的方法，以避免浮点限制导致问题，其中，最接近理论结果的可表示双精度可以是整数，尽管实际结果不是整数。这只会发生在n值非常大的情况下，但是。。。在