[C/C++] Project Euler #39 - Integer Right Triangles

Project Euler #39 is a relatively easy problem with a difficulty rating of 5%. As the title suggests, it is about Pythagorean triangles.

 

A Pythagorean triangle is a right triangle where all side lengths are integers. The fundamental relationship for such a triangle follows the well-known Pythagorean theorem:

 

\[ a^2 + b^2 = c^2 \]

 

If there exists an integer triplet (x, y, z) satisfying the equation above, then for any constant c , the triplet (cx, cy, cz) will also satisfy the Pythagorean theorem. A primitive Pythagorean triple consists of numbers that are coprime with each other. The method to generate these primitive triples is straightforward and is frequently used in many Project Euler problems.

 

Given two numbers m and n , if (m, n) = 1 (i.e., they are coprime) and m+n is odd, then the following formulas generate a primitive Pythagorean triple:

 

\( a = m^2 - n^2, \quad b = 2mn, \quad c = m^2 + n^2 \)

 

 

Pythagorean triangles

 

To solve this problem, I first identified all primitive Pythagorean triples within the given number range. Then, I checked whether each possible perimeter length is a multiple of any of these triples.

//------------------------------------------------
//    Project Euler #39 - Integer Right Triangles
//        - by Aubrey Choi
//        - created at 2015-03-22
//------------------------------------------------
#include <stdio.h>

#define    MAXLEN    1000

int gcd(int a, int b);

int main()
{
    int s, t;
    int pn[10000];
    int count = 0;

    for( int s = 2 ; s*s < MAXLEN/2 ; s++ )
    {
        for( int t = s-1 ; t >= 1 ; t -= 2 )
        {
            if( gcd(s, t) != 1 ) continue;

            int len = 2*s*s + 2*s*t;
            if( len > MAXLEN ) break;

            pn[count++] = len;
        }
    }

    int max = 0;
    int maxlen = 0;
    for( int i = pn[0] ; i <= 1000 ; i++ )
    {
        int t = 0;
        for( int j = 0 ; j < count ; j++ )
            if( i%pn[j] == 0 ) t++;
        if( max < t ) { max = t; maxlen = i; }
    }

    printf("ans = %d\n", maxlen);
}

int gcd(int a, int b)
{
    while( b )
    {
        int t = b;
        b = a%b;
        a = t;
    }
    return a;
}

 

The function gcd(a, b) computes the greatest common divisor (GCD) of a and b, ensuring that m and n are coprime, as required by the conditions for generating primitive triples.

 

In the first part of the main() function, the program computes primitive Pythagorean triples and stores their perimeter lengths in the array pn[].

 

In the second part, it iterates through all numbers from pn[0] to 1000, checking how many times each perimeter length can be evenly divided by the values in pn[]. The perimeter length with the maximum count is then stored as maxlen.

 

This program can be further optimized for speed, which becomes crucial for more complex Project Euler problems like #78, where efficiency is necessary to obtain a solution within a reasonable time.