Anonymous user
Pythagorean triples: Difference between revisions
+Arbitrary precision Java
m ("divisor", bah) |
(+Arbitrary precision Java) |
||
Line 1:
{{draft task}}
A [[wp:Pythagorean_triple|Pythagorean triple]] is defined as three positive integers <math>(a, b, c)</math> where <math>a\leq b\leq c</math>, and <math>a^2+b^2=c^2.</math>
How many Pythagorean triples are there with a perimeter no larger than 100? Of these, how many are primitive?▼
▲How many Pythagorean triples are there with a perimeter no larger than 100?
Extra: Can your program handle a max perimeter of 1,000,000? What about 10,000,000? 100,000,000?▼
▲'''Extra credit:''' Can your program handle a max perimeter of 1,000,000?
=={{header|C}}==
Line 38 ⟶ 39:
return 0;
}</lang>output:<lang>Up to 100, there are 17 triples, of which 7 are primitive</lang>
=={{header|Java}}==
[[Category:Arbitrary precision]]Theoretically, this can go "forever", but it takes a while, so only the minimum is shown. Luckily, <code>BigInteger</code> 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:
<pre>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.</pre>
| |||