Pythagorean triples
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 divisors . 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 credit: 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>
Java
Theoretically, this can go "forever", but it takes a while, so only the minimum is shown. Luckily, BigInteger
has a GCD method built in.
<lang java>import java.math.BigInteger;
public class PythTrip { public static void main(String[] args){ long tripCount = 0, primCount = 0;
//change this to whatever perimeter limit you want;the RAM's the limit BigInteger periLimit = new BigInteger("100");
for(BigInteger a = BigInteger.ONE; a.compareTo(periLimit) < 0; a = a.add(BigInteger.ONE)){ for(BigInteger b = new BigInteger(a.toString()); b.compareTo(periLimit) < 0; b = b.add(BigInteger.ONE)){ for(BigInteger c = new BigInteger(b.toString()); c.compareTo(periLimit) < 0; c = c.add(BigInteger.ONE)){ if(a.add(b).add(c).compareTo(periLimit) > 0)break; if(a.pow(2).add(b.pow(2)).compareTo(c.pow(2)) != 0) continue;
tripCount++; System.out.print(a +", "+b+", "+c);
//does binary GCD under the hood if(a.gcd(b).compareTo(BigInteger.ONE) == 0){ System.out.print(" primitive"); primCount++; } System.out.println(); } } } System.out.println("Up to a perimeter of "+periLimit+", there are "+ tripCount+" triples, of which "+primCount+" are primitive."); } }</lang> Output:
3, 4, 5 primitive 5, 12, 13 primitive 6, 8, 10 7, 24, 25 primitive 8, 15, 17 primitive 9, 12, 15 9, 40, 41 primitive 10, 24, 26 12, 16, 20 12, 35, 37 primitive 15, 20, 25 15, 36, 39 16, 30, 34 18, 24, 30 20, 21, 29 primitive 21, 28, 35 24, 32, 40 Up to a perimeter of 100, there are 17 triples, of which 7 are primitive.