ユークリッドの互除法をperlで書いてみました。
use strict; use warnings; { gcd(160,48); } sub gcd { my ($x, $y) = @_; my $c; while ($x > 0 && $y > 0) { if ($y > $x) { $c = $x; $x = $y; $y = $c; } print "$x, $y\n"; $c = $y; $x = $x - $y; $y = $c; } }
表示結果は下記のようになり、2つの自然数の最大公約数が求まります。
160, 48
112, 48
64, 48
48, 16
32, 16
16, 16
引き算で求まっていくのが不思議です。ということで、どういう感じで求まっていくのかを確かめてみました。
という感じになりますね。