圆的整数解的算法？

Question

我正在尝试搜索方程的整数解：

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中做到这一点，以使其运行时间大大缩短？

注意：我已经看到了这个问题，但是它是关于在圆内找到晶格点，而不是圆方程的整数解。我也有兴趣寻找特定的解决方案，而不仅仅是解决方案的数量。

编辑：我仍在寻找更快数量级的东西。这是一个示例：n = 5应该具有12个整数解，以找到应该在Wolfram alpha上搜索该方程的整数。

编辑2：@victor zen对这个问题给出了惊人的答案。谁能想到进一步优化其解决方案的方法？

Answer 1

在算法中，您正在搜索所有可能的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值：

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