如何优化算法以将数字分解为两个平方的总和？

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)那时i*i + j*j将大于n任何j大于i.
  • (只有平方根n,因为
• 减去平方 i
• 取结果的平方根,找到最接近的整数 - 调用它 j
• 检查您感兴趣的条件是否成立

最后两个步骤实际上只是检查平方根n - i*i实际上是一个整数,但在某些情况下(对于非常大的n值)找到最接近的整数然后检查条件可能是一种更可靠的方法,以避免引起问题的浮点限制,尽管实际结果不是整数,但理论结果的最近可表示的两倍可以是整数.这只会发生在非常大的n值,但......