26 lines
1.2 KiB
Plaintext
26 lines
1.2 KiB
Plaintext
A [[wp:Pythagorean_triple|Pythagorean triple]] is defined as three positive integers <math>(a, b, c)</math> where <math>a < b < c</math>, and <math>a^2+b^2=c^2.</math>
|
|
|
|
They are called primitive triples if <math>a, b, c</math> are co-prime, that is, if their pairwise greatest common divisors <math>{\rm gcd}(a, b) = {\rm gcd}(a, c) = {\rm gcd}(b, c) = 1</math>.
|
|
|
|
Because of their relationship through the Pythagorean theorem, a, b, and c are co-prime if a and b are co-prime (<math>{\rm gcd}(a, b) = 1</math>).
|
|
|
|
Each triple forms the length of the sides of a right triangle, whose perimeter is <math>P=a+b+c</math>.
|
|
|
|
|
|
;Task:
|
|
The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.
|
|
|
|
|
|
;Extra credit:
|
|
Deal with large values. Can your program handle a maximum perimeter of 1,000,000? What about 10,000,000? 100,000,000?
|
|
|
|
Note: the extra credit is not for you to demonstrate how fast your language is compared to others; you need a proper algorithm to solve them in a timely manner.
|
|
|
|
|
|
;Related tasks:
|
|
* [[Euler's sum of powers conjecture]]
|
|
* [[List comprehensions]]
|
|
* [[Pythagorean quadruples]]
|
|
<br><br>
|
|
|