Project Euler - 09

[Petcheco]

Hey, guys.

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.

#include <iostream>

using namespace std;

int a = 0; int b = 0; int c = 0;
bool Found = false;

int Find_Triplet(int,int,int);

int Find_Triplet(int a, int b, int c)
{
for (int i = 5; i < 1000; i++)
{
    c = i;
    for (int j = 2; j < c; j++)
    {
        b = j;
        for (int k = 1; k < b; k++)
        {
             a = k;
            if (a*a + b*b == c*c && a+b+c == 1000)
            {
                Found = true;
                break;
            }
        }
        if (Found)
            break;
    }
    if (Found)
        break;
}
return a*b*c;
}

int main()
{
    cout << Find_Triplet(a,b,c) << endl;
    return 0;
}

How can I improve my program?

Thank you.

Petcheco

[ddanbe]

The only time Found will be true is when the condition on line 21 is true. There you break and use Found to break out of the other loops. Use a goto label here! This is one of those rare conditions where a goto is useful. I think even Stroustrup says so in his book.

[Petcheco]

Thank you, sir.

[StuXYZ]

Fundermentally, the loops are highly inefficient.

You have the condition that a+b+c == 1000, so why not loop on a and b BUT calcuate c.

Second you can limit the loop extent based on the idea that c>b>a.
Thus a can never go beyond 333 (1000/3) and b extends from a+1
to 1000-3*a.

This would leave you with two loops only.

// THIS is a long way off efficient.

for(int a=1;a<333;a++)  // b>a and a>c thus (3*a)<1000
  for(int b=a+1;b<1000-3*a;b++)
     {
       int c=1000-a-b; 
       if (a*a+b*b==c*c)
         return SUCCESS;
     }
 return FAILED;

[Petcheco]

Thank you, mate.

[Petcheco]

a can't be bigger than c.

if we have a²+b² = c², than c > b >= a.

[Petcheco]

Edited my code. It looks like

#include <iostream>

using namespace std;

int a = 0; int b = 0; int c = 0;

int Find_Triplet(int,int,int);

int Find_Triplet(int a, int b, int c)
{
for (a= 5; a < 500; a++)
{
    for (b = 2; b < a; b++)
    {

        c = 1000-a-b;
            if (a*a + b*b == c*c && a+b+c == 1000)
            {
                goto End_of_Loop;
            }
        }
    }

End_of_Loop:
return a*b*c;
}

int main()
{
    cout << Find_Triplet(a,b,c) << endl;
    return 0;
}

this now.

Any tips?

[NathanOliver]

Don't use goto. In this case to get out of your nested loops just use return a*b*c; where you have goto End_of_Loop;. There is no point exiting out of the loops to get to the return statement when return will kill the function for you.

[Petcheco]

Thank you, Nathan.