Project Euler Problem 9

Problem 9

a, b, cは全て自然数で、a < b < cかつa + b + c = 1000であるから、
0 < a < 1000/3, a < b < (1000-a)/2, c = 1000 - (a+b)という条件の下で調べれば良い。

証明:
a + b + c = 1000より、c = 1000 - (a+b)となり、b < cに代入すると、
b < 1000 - (a+b)
<=> b < (1000-a)/2
よって、a < b < (1000-a)/2となる。
またこれより、
a < (1000-a)/2
<=> a < 1000/3
よって、0 < a < 1000/3となる。

Scheme

(use srfi-42)

(define n 1000)
(define (p009)
  (print (car (list-ec (: a (floor (/ n 3)))
                       (: b a (floor (/ (- n a) 2)))
                       (:let c (- n a b))
                (if (eq? (+ (* a a) (* b b)) (* c c)))
                (* a b c)))))

(p009)

C++

#include <cstdio>

int main()
{
    for (int a = 1; a < 1000/3; a++)
    for (int b = a; b < (1000-a)/2; b++)
    {
        int c = 1000-(a+b);
        if (a*a+b*b==c*c) {
            printf("%d\n", a*b*c);
            goto end;
        }
    }
end:
    return 0;
}