Project Euler Solution 9

Problem Statement

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,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Solution

It is difficult and time consuming to find out Pythagoren triplet if we program with all combinations of natural numbers starting from 1.

The a,b and c in the Pythagorean triplet represents three sides of a right angled triangle. We know that In a right angled triangle, square of the hypotenuse is equal to the sum of the squares of the other two sides namely opposite side and adjacent side. That is given in the problem as

a² + b² = c²

It is easy to find pythagorian triples using Euclid’s Formula. To know more about Pythogorean triples click here.

According to Euclid’s theorem, for any two positive integers m and n where m>n, the three sides of the triangle are

a = m² - n²

b = 2mn

c = m² + n²

So now its easy to find a Pythogorean triplet using above, and our job is to just check if

a + b + c = 1000

Implementation

#include <stdio.h>
int main(){    int m, n, side_a, side_b, side_c;    for (m = 2;; m++)    {        for (n = 1; n < m; n++)        {            side_a = (m *m) - (n *n);            side_b = 2 *(m *n);            side_c = (m *m) + (n *n);            if ((side_a + side_b + side_c) == 1000)            {                printf("%d", side_a *side_b *side_c);                return 0;            }        }    }}

Sample Output