python - 圆的整数解的算法？

我试图寻找方程的整数解：

y^2 + x^2 = 2n^2

如果我在wolfram alpha中搜索这个，它们几乎都会立即被找到，即使是非常大的n。当我实现一个蛮力方法时，速度非常慢：

def psearch(n, count):
    for x in range(0, n):
        for y in range(0, n):
            if x*x + y*y == 2*n**2:
                print(x,y)
                count += 1
    return count

所以我假设有一个更快的方法得到上面方程的所有整数解。我如何在python中做到这一点，以便它有更低的运行时？
注：我已经看到this question但是它是关于在一个圆内找到晶格点，而不是圆方程的整数解。另外，我感兴趣的是找到具体的解决方案，而不仅仅是解决方案的数量。
编辑：我仍然在寻找一个数量级更快的东西。下面是一个例子：n=5应该有12个整数解，以找到应该在Wolfram alpha上搜索这个方程的解。
编辑2:@维克多·岑对这个问题给出了惊人的答案。有谁能想出进一步优化解决方案的方法吗？

最佳答案

在你的算法中，你在搜索所有可能的y值。这是不必要的。这里的诀窍是要意识到

y^2 + x^2 = 2n^2

直接意味着

y^2 = 2n^2-x^2

这意味着你只需要检查2n^2-x^2是一个完美的正方形。你可以通过

y2 = 2*n*n - x*x
#check for perfect square
y = math.sqrt(y2)
if int(y + 0.5) ** 2 == y2:
    #We have a perfect square.

另外，在你的算法中，你只检查x值到n。这是不正确的。由于y^2始终为正或零，我们可以通过将y^2设置为其最低值（即0）来确定需要检查的最高x值。因此，我们需要检查所有满足

x^2 <= 2n^2

减少到

abs(x) <= sqrt(2)*n.

将此与只检查顶部象限的优化结合起来，您将得到一个优化的psearch

def psearch(n):
    count = 0
    top = math.ceil(math.sqrt(2*n*n))
    for x in range(1, top):
        y2 = 2*n*n - x*x
        #check for perfect square
        y = math.sqrt(y2)
        if int(y + 0.5) ** 2 == y2:
            count+=4
    return count