Pythagorean triples: Difference between revisions
Content added Content deleted
imported>Maxima enthusiast |
(Added Algol 68) |
||
Line 381: | Line 381: | ||
Up to 10 ** 8 : 113236940 Triples, 7023027 Primitives |
Up to 10 ** 8 : 113236940 Triples, 7023027 Primitives |
||
Up to 10 ** 9 : 1294080089 Triples, 70230484 Primitives</pre> |
Up to 10 ** 9 : 1294080089 Triples, 70230484 Primitives</pre> |
||
=={{header|ALGOL 68}}== |
|||
Uses a table of square roots so OK for perimeters up to 1000 (or possibly 10 000), for larger perimeters, binary searching a table of squares to find the root would probably be better... |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find some Pythagorean triples ( a, b, c ) # |
|||
# where a < b < c and a^2 + b^2 = c^2 # |
|||
INT max perimeter = 100; # maximum a + b + c we will consider # |
|||
INT max square = max perimeter * max perimeter; |
|||
# form a table of square roots of numbers to max perimeter ^ 2 # |
|||
[ 1 : max square ]INT sr; |
|||
FOR i TO UPB sr DO sr[ i ] := 0 OD; |
|||
FOR i TO max perimeter DO sr[ i * i ] := i OD; |
|||
PROC gcd = ( INT x, y )INT: # iterative gcd # |
|||
BEGIN |
|||
INT a := ABS x, b := ABS y; |
|||
WHILE b /= 0 DO |
|||
INT next a = b; |
|||
b := a MOD b; |
|||
a := next a |
|||
OD; |
|||
a |
|||
END # gcd # ; |
|||
# count the Pythagorean triples # |
|||
INT t count := 0, p count := 0; |
|||
FOR a TO max perimeter DO |
|||
INT a2 = a * a; |
|||
FOR b FROM a + 1 TO max perimeter - a |
|||
WHILE INT c = sr[ a2 + ( b * b ) ]; |
|||
a + b + c <= max perimeter |
|||
DO IF c > b THEN # have a triple # |
|||
t count +:= 1; |
|||
IF gcd( a, b ) = 1 THEN # have a primitive triple # |
|||
p count +:= 1 |
|||
FI |
|||
FI |
|||
OD |
|||
OD; |
|||
print( ( "Pythagorean triples with perimeters up to ", whole( max perimeter, 0 ), ":", newline ) ); |
|||
print( ( " Primitive: ", whole( p count, 0 ), newline ) ); |
|||
print( ( " Total: ", whole( t count, 0 ), newline ) ) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Pythagorean triples with perimeters up to 100: |
|||
Primitive: 7 |
|||
Total: 17 |
|||
</pre> |
|||
=={{header|Arturo}}== |
=={{header|Arturo}}== |