A 1000 Pythagorean triplets - 我的博客 - ITeye技术网站

A 1000 Pythagorean triplets - 我的博客 - ITeye技术网站
http://www.mathblog.dk/pythagorean-triplets/

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.

Brute Force

For the brute force algorithm we would need to loop over all the possible values of a and b, calculatec and check if that is a solution. We could be ignorant and just let a and b loop from 1-1000, or we could use the facts that a < b < c, and thus exploit that  a < s/3,  and a < b < s/2.

1. int a = 0, b = 0, c = 0;  
2. int s = 1000;  
3. bool found = false;  
4. for (a = 1; a < s / 3; a++) {  
5.     for (b = a; b < s / 2; b++) {  
6.         c = s - a - b;  
7.         if (a * a + b * b == c * c) {  
8.             found = true;  
9.             break;  
10.         }  
11.     }  
12.    
13.     if (found) {  
14.         break;  
15.     }  
16. }  

Read full article from A 1000 Pythagorean triplets - 我的博客 - ITeye技术网站