Python程序：计算指定范围内的勾股三元组

勾股数是指满足勾股定理 $a^2 + b^2 = c^2$ 的三个正整数 $(a, b, c)$ 。其中 $a$ 、 $b$ 、 $c$ 两两互质，又称原始勾股数。

在自然数 $N$ 的范围内，找出所有满足勾股定理的三元组 $(a, b, c)$ ，即 $a^2 + b^2 = c^2$ ，且 $a, b, c$ 均为自然数，并且 $a\leqb\leqc\leqN$ 。

思路分析

Python语言编写代码来计算指定范围内的勾股三元组步骤如下：

输入自然数 N 的值。
枚举每一个可能的三元组 $(a,b,c)$ ，并判断其是否满足勾股定理。
输出所有满足勾股定理的三元组 $(a,b,c)$ 。

基本实现

我们可以根据上述思路基本实现一个 Python 程序，如下所示：

# 输入自然数 N
N = int(input())

# 枚举所有可能的三元组
for a in range(1, N+1):
    for b in range(a, N+1):
        for c in range(b, N+1):
            if a * a + b * b == c * c:
                print(a, b, c)

上面代码使用了三个 for 循环，依次枚举出所有可能的三元组 $(a,b,c)$ ，然后判断其是否为勾股数，如果是，则输出其三个正整数 $a$ , $b$ , $c$ 的值。

剪枝优化

在基本实现中，我们使用了三层循环枚举每一个可能的三元组，但是这样做效率比较低。因为大部分枚举都是不必要的，例如当 $a = 1$ 时，枚举 $b$ 的范围应该是 $[2,N]$ ，而不是 $[1,N]$ ，因为当 $b = 1$ 时， $a^2 + b^2 = 1^2 + 1^2 ，显然不满足勾股定理。$

因此，我们可以通过一些剪枝技巧，来减少不必要的枚举。比如，我们可以根据勾股定理，把 $c$ 的上限缩小为 $c<\sqrt{2}N$ ，即 $a^2 + b^2<(\sqrt{2}N)^2$ 。又由于 $a\leqb\leqc$ ，因此我们可以进一步缩小 $a$ 和 $b$ 的范围，将 $b$ 的上限降到 $b<\sqrt{2}N$ ，将 $a$ 的上限降到 $a<\sqrt{2}N$ 。

更新后的 Python 程序如下：

# 输入自然数 N
N = int(input())

# 枚举所有可能的三元组
for a in range(1, int((2**0.5)*N)+1):
    for b in range(a, int((2**0.5)*N)+1):
        c2 = a*a + b*b
        c = int(c2**0.5)
        if c*c == c2 and c <= N:
            print(a, b, c)

上述程序一次枚举所需的时间复杂度为 $\mathcal{O}(N^2\log N)$ ，空间复杂度为 $\mathcal{O}(1)$ 。

更进一步的优化

上面的剪枝技巧已经可以大大减少枚举数量，但是在判断是否为勾股数时，我们还可以采用更高效的方法。

勾股数必须满足 $a, b, c$ 两两互质，因此我们可以使用 Euclid 算法来快速判断两个数是否互质。另外，如果存在一个正整数 $k$ ，使得 $a=k m^2$ ， $b=k n^2$ ， $c=k(m^2+n^2)$ ，其中 $m>n$ ，那么 $(a,b,c)$ 就是勾股数。因此，我们可以在枚举 $a,b$ 时，根据 $a=k m^2$ ， $b=k n^2$ ，求解出 $c$ 的值，然后再检查 $c$ 是否为正整数，并且是否满足 $a, b, c$ 两两互质。

更新后的 Python 程序如下：

# 输入自然数 N
N = int(input())

# 枚举所有可能的三元组
for m in range(2, int((2**0.5)*N)+1):
    for n in range(1, m):
        if (m - n) % 2 == 1 and math.gcd(m, n) == 1:
            k = 1
            while k*(m**2+n**2) <= N:
                a = k*(m**2-n**2)
                b = k*2*m*n
                c = k*(m**2+n**2)
                print(a, b, c)
                k += 1

上述程序一次枚举所需的时间复杂度为 $\mathcal{O}(N\log N)$ ，空间复杂度为 $\mathcal{O}(1)$ ，速度比前面的程序快了数倍。