Finding Pythagorean Triples: Euclid's Formula

Question

I'm working on problem 9 in Project Euler:

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

The following code I wrote uses Euclid's formula for generating primes. For some reason my code returns "0" as an answer; even though the variable values are correct for the first few loops. Since the problem is pretty easy, some parts of the code aren't perfectly optimized; I don't think that should matter. The code is as follows:

#include <iostream>
using namespace std;

int main()
{
    int placeholder;    //for cin at the end so console stays open
    int a, b, c, m, n, k;
    a = 0;  b = 0;  c = 0;
    m = 0;  n = 0;  k = 0;  //to prevent initialization warnings
    int sum = 0;
    int product = 0;

    /*We will use Euclid's (or Euler's?) formula for generating primitive
     *Pythagorean triples (a^2 + b^2 = c^2): For any "m" and "n",
     *a = m^2 - n^2 ; b = 2mn ; c = m^2 + n^2 . We will then cycle through
     *values of a scalar/constant "k", to make sure we didn't miss anything.
     */

    //these following loops will increment m, n, and k,
    //and see if a+b+c is 1000. If so, all loops will break.
    for (int iii = 1; m < 1000; iii++)
    {
        m = iii;
        for (int ii = 1; n < 1000; ii++)
        {
            n = ii;
            for (int i = 1; k <=1000; i++)
            {
                sum = 0;
                k = i;
                a = (m*m - n*n)*k;
                b = (2*m*n)*k;
                c = (m*m + n*n)*k;
                if (sum == 1000) break;
            }
            if (sum == 1000) break;
        }
        if (sum == 1000) break;
    }
    product = a * b * c;

    cout << "The product abc of the Pythagorean triplet for which a+b+c = 1000 is:\n";
    cout << product << endl;
    cin >> placeholder;
    return 0;
}

And also, is there a better way to break out of multiple loops without using "break", or is "break" optimal?

---

Here's the updated code, with only the changes:

for (m = 2; m < 1000; m++)
    {
        for (int n = 2; n < 1000; n++)
        {
            for (k = 2; (k < 1000) && (m > n); k++)
            {
                sum = 0;
                a = (m*m - n*n)*k;
                b = (2*m*n)*k;
                c = (m*m + n*n)*k;
                sum = a + b + c;
                if ((sum == 1000) && (!(k==0))) break;
            }

It still doesn't work though (now gives "1621787660" as an answer). I know, a lot of parentheses.

Answer 1

The new problem is that the solution occurs for k = 1, so starting your k at 2 misses the answer outright.

Instead of looping through different k values, you can just check for when the current sum divides 1000 evenly. Here's what I mean (using the discussed goto statement):

      for (n = 2; n < 1000; n++)
        {
          for (m = n + 1; m < 1000; m++)
            {
              sum = 0;
              a = (m*m - n*n);
              b = (2*m*n);
              c = (m*m + n*n);
              sum = a + b + c;
              if(1000 % sum == 0)
                {
                  int k = 1000 / sum;
                  a *= k;
                  b *= k;
                  c *= k;
                  goto done;
                }
            }
        }
     done:
      product = a * b * c;

I also switched around the two for loops so that you can just initialize m as being larger than n instead of checking every iteration.

Note that with this new method, the solution doesn't occur for k = 1 (just a difference in how the loops are run, this isn't a problem)

Answer 2

Presumably sum is supposed to be a + b + c. However, nowhere in your code do you actually do this, which is presumably your problem.

To answer the final question: Yes, you can use a goto. Breaking out of multiple nested loops is one of the rare occasions when it isn't considered harmful.