生成毕达哥拉斯三元组的最佳方法是什么？

Question

我试过用一段简单的代码，检查所有可能的a和b组合，然后看看c的平方根是不是整数，但那段代码运行得非常慢。接着，我尝试了欧几里得的公式。

a = d*(n^2 - m^2)
b = 2*n*m*d
c = d*(n^2 + m^2)

我写了一段代码，首先用

trunc(sqrt(max_value))
//this is in pascal

找到n，然后检查每个0 < m < n的组合。但是我得到了重复的结果，比如当n是7，m是5，d是1时，还有n是6，m是1，d是2的情况。在这两种情况下，结果都是24、70和74。所以，有没有什么好的快速方法来计算毕达哥拉斯三元组的数量？我似乎找不到办法。而且如果我把所有结果放到一个数组里，然后再检查数组中的重复项，这样也太耗时了……如果有人能帮我写代码，使用pascal、c或者python都可以，我都能理解……

Answer 1

我很好奇，所以决定试一下。我发现这个算法在Python中实现起来非常简单，而且运行速度也很快：

import math                                                                 

def pythagorean_triples(n):                                                 
    a, b, c = 1, 3, 0                                                       
    while c < n:                                                            
        a_ = (a * b) + a                                                    
        c = math.sqrt(a_**2 + b**2)                                         
        if c == int(c):                                                     
            yield b, a_, int(c)                                             
        a += 1                                                              
        b += 2                                                              

if __name__ == '__main__':                                                  
    import sys                                                              
    for pt in pythagorean_triples(int(sys.argv[1])):                        
        print(pt)

你可以把这个脚本复制到pythagorean_triples.py文件中，然后运行python3 pythagorean_triples.py n，其中n是你想生成的最大c值。（如果你愿意，也可以使用后来的Python2。）

Answer 2

维基百科关于毕达哥拉斯三元组的页面给了我们一些提示：

根据欧几里得的公式生成的三元组是原始的，当且仅当 m 和 n 是互质的，并且 m - n 是奇数。如果 m 和 n 都是奇数，那么 a、b 和 c 都会是偶数，这样生成的三元组就不是原始的；不过，如果 m 和 n 是互质的，除以 2 后，a、b 和 c 就会变成一个原始的三元组。

如果你把 m 和 n 限制为互质的数字，并且让 m - n 是奇数，你就能唯一地生成所有的原始毕达哥拉斯三元组。从这个点开始，你可以把这些独特的三元组乘以一个因子 d，来唯一生成所有的三元组。

在你的例子中，允许 n=7 和 m=5 是个问题，因为它们的差是偶数，生成的三元组不是原始的（你可以把所有边都除以 2，得到一个更小的三元组）。