Pythagorean triples: Difference between revisions
(some clarification) |
(sample (bad) code) |
||
Line 6: | Line 6: | ||
Extra: Can your program handle a max perimeter of 1,000,000? What about 10,000,000? 100,000,000? |
Extra: Can your program handle a max perimeter of 1,000,000? What about 10,000,000? 100,000,000? |
||
=={{header|C}}== |
|||
Sample implemention; naive method, patently won't scale to larger numbers. |
|||
<lang C>#include <stdio.h> |
|||
int gcd(int m, int n) |
|||
{ |
|||
int t; |
|||
while (n) { t = n; n = m % n; m = t; } |
|||
return m; |
|||
} |
|||
int main() |
|||
{ |
|||
int a, b, c; |
|||
int pytha = 0, prim = 0; |
|||
for (a = 1; a < 100; a++) { |
|||
for (b = a; b < 100; b++) { |
|||
for (c = b; c < 100; c++) { |
|||
if (a + b + c > 100) break; |
|||
if (a * a + b * b != c * c) continue; |
|||
pytha++; |
|||
if (gcd(a, b) == 1) prim++; |
|||
} |
|||
} |
|||
} |
|||
printf("Up to 100, there are %d triples, of which %d are primitive\n", |
|||
pytha, prim); |
|||
return 0; |
|||
}</lang>output:<lang>Up to 100, there are 17 triples, of which 7 are primitive</lang> |
Revision as of 15:59, 28 June 2011
A Pythagorean triple is defined as three positive integers where , and They are called primitive triples if are coprime, that is, if their pairwise greatest common denominators . Each triple form the length of the sides of a right triangle, whose perimeter is .
Task
How many Pythagorean triples are there with a perimeter no larger than 100? Of these, how many are primitive?
Extra: Can your program handle a max perimeter of 1,000,000? What about 10,000,000? 100,000,000?
C
Sample implemention; naive method, patently won't scale to larger numbers. <lang C>#include <stdio.h>
int gcd(int m, int n) { int t; while (n) { t = n; n = m % n; m = t; } return m; }
int main() { int a, b, c; int pytha = 0, prim = 0; for (a = 1; a < 100; a++) { for (b = a; b < 100; b++) { for (c = b; c < 100; c++) { if (a + b + c > 100) break; if (a * a + b * b != c * c) continue;
pytha++; if (gcd(a, b) == 1) prim++; } } }
printf("Up to 100, there are %d triples, of which %d are primitive\n", pytha, prim); return 0; }</lang>output:<lang>Up to 100, there are 17 triples, of which 7 are primitive</lang>