Problem 9
A Pythagorean triplet is a set of three natural numbers, a 
b c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
Solution 1
using System;
namespace ProjectEulerCSharp_009
{
class Program
{
static void Main(string[] args)
{
int iterations = 0;
for (int a = 1; a <= 998; a++)
{
for (int b = 1; b <= 998; b++)
{
int c = 1000 – (a + b);
iterations++;
if (a * a + b * b == c * c)
{
System.Console.WriteLine("{0}", a*b*c);
System.Console.WriteLine(iterations);
return;
}
}
}
}
}
}
Solution 2
using System;
namespace ProjectEulerCSharp_009
{
class Program
{
static void Main(string[] args)
{
int iterations = 0;
for (int a = 1; a <= 998; a++)
{
for (int b = a + 1; b <= 998; b++)
{
int c = 1000 – (a + b);
iterations++;
if (a * a + b * b == c * c)
{
System.Console.WriteLine("{0}", a*b*c);
System.Console.WriteLine(iterations);
return;
}
}
}
}
}
}
Solution 3
using System;
namespace ProjectEulerCSharp_009
{
class Program
{
static void Main(string[] args)
{
int iterations = 0;
for (int a = 1; a <= 998; a++)
{
for (int b = a + 1; a + b < 1000; b++)
{
int c = 1000 – (a + b);
iterations++;
if (a * a + b * b == c * c)
{
System.Console.WriteLine("{0}", a*b*c);
System.Console.WriteLine(iterations);
return;
}
}
}
}
}
}
Solution 4
using System;
namespace ProjectEulerCSharp_009
{
class Program
{
static void Main(string[] args)
{
int iterations = 0;
for (int a = 1; a <= 998; a++)
{
for (int b = a + 1; a + b < 1000; b++)
{
int c = 1000 – (a + b);
if (c <= b) { break; }
iterations++;
if (a * a + b * b == c * c)
{
System.Console.WriteLine("{0}", a*b*c);
System.Console.WriteLine(iterations);
return;
}
}
}
}
}
}
Discussion
I am a big fan of getting the code working then optimizing later. I wanted to demonstrate that process with those post so I have included 4 iterations of optimizations.
If we were to loop through all of the possible digits from 1 through 998 twice (once for a and once for b) we would end up doing 996,004 iterations. That’s our baseline.
Solution 1
Because they state that there is only 1 solution, as soon as we find it there is no reason to continue. The obvious optimization is to exit the loops once we’ve found it. This brings our iterations to 198,778.
Solution 2
If we realize that we only need to check the numbers where b is greater than a then we can save ourselves and addition 20,000 iterations bringing our new number to 178678.
Solution 3
Knowing that another condition is that a + b + c = 1000 then a + b has to be less than 1000. This saves nearly 20,000 iterations as well. We are down to 159,716 iterations.
Solution 4
Finally, knowing that c has to be greater than b we can cut the iterations by 90,000 to : 69676.
That makes us about 14 times faster than the original version. There are going to be some additional optimizations you can make, but how fast do you need it? On my laptop, the difference is imperceptible. I could have left it at the original and been quite happy.
If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).
azzlsoft.com 