Finding all the Pythagorean triples

[markgritter]

My interest was sparked by this Quora question: How would you find all the Pythagorean triplets in an array of N numbers? The first answer was the straightforward O(N^2) examination of all pairs of numbers. It seemed like there might be a better way. One of the comments initially suggested O(N^2) was probably the best possible, because of its

Comments

[barking_iguana]

As you may know, there is a one-to-tone correspondence between irreducible Pythagorean Triples and sets of Natural Numbers {M, N}, where M > N, M and N are mutually prime and one of them is even. The sets where M and N have common factors or are both odd generate triples that are reducible. The Legs are M^2 - N^2 and 2MN. The Hypotenuse is M^2 + N^ 2.

Is that useful in limiting the search space?

[markgritter]

I thought about that, it seems like it should give an alternate way of enumerating all the primitive pythagorean triples (with bounded hypotenuse), although I do not know if it is possible to enumerate the M and N efficiently due the relative primality constraint (for example, if we have to run gcd for every possible pair?)

I did not see any way to apply it to the search in a more direct fashion.

[barking_iguana]

Iterate on factors?