PhoenixWright

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.
A Pythagorean triplet is a set of three natural numbers, a<b<c, for which,

Euclid’s formula is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers

form a Pythagorean triple. The triple generated by Euclid’s formula is primitive if and only if m and n are coprime and one of them is even.(Reference:Pythagorean Triple)
The following will generate all Pythagorean triples:

So a+b+c=m(m+n)*2d=S, let k=m+n, because only one of m and n is even, k will be a odd number.We have to find a divisor m of S/2 and a odd divisor k of S/(2mn) with m < k < 2m and gcd(m,k)=1.
Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <math.h>
#include <stdio.h>
 
using namespace std;
int gcd(int a, int b) {
    return (!b)?a:gcd(b, a%b);
}
int main() {
    int s = 1000;
    int ts = s / 2;
    int limit = sqrt(ts);
    int tm, m, k, n, d, a, b, c;
    for(m = 2; m <= limit; ++m) if(ts % m == 0) {
        if(m & 1) k = m + 2;
        else k = m + 1;
        tm = ts / m;
        while(!(tm&1)) tm >>= 1;
        for(; k < 2 * m && k <= tm; k += 2) if(tm % k == 0 && gcd(m, k) == 1) {
            d = ts / m / k;
            n = k - m;
            a = (m*m-n*n) * d;
            b = 2 * m * n * d;
            c = (m*m+n*n) * d;
            printf("%d*%d*%d=%dn", a, b, c, a * b * c);
        }
    }
    return 0;
}