最大公約数・最小公倍数の求め方。

ユークリッド互除法による最大公約数の求め方。

大きい方から小さい方を引き，小さい方の数と引いてできた数で同様に引いていく．
同じ数字が並んだら答．
例)
18と10の場合
18-10=8
10-8=2
8-2=6
6-2=4
4-2=2 -> 同じ数(2)が続いたので答え!
答え:2

最小公倍数の求め方。
AB=GL から求める                    ※(Gは最大公約数,Lは最小公倍数)
つまり、L=AB/G
上記の場合、最大公約数は2であるため、
AB=18*10=180/2=90
答え:90

以下、active perl で書いたサンプルです。

#!perl
#euclidean.pl
#ユークリッド互除法による最大公約数の求め方。
#大きい方から小さい方を引き，小さい方の数と引いてできた数で同様に引いていく．
#同じ数字が並んだら答．
#例)
#18と10の場合
#18-10=8
#10-8=2
#8-2=6
#6-2=4
#4-2=2 -> 同じ数(2)が続いたので答え!
#答え:2
#
#最小公倍数の求め方。
#AB=GL から求める                    ※(Gは最大公約数,Lは最小公倍数)
#つまり、L=AB/G
#上記の場合、最大公約数は2であるため、
#AB=18*10=180/2=90
#答え:90

my $a1;
my $b1;
my $a = 12;
my $b = 69;
my $d = -1;
my $n = 0;
my $g;
my $l;

print "二つの数をコンマで区切って入力してください。:";
my $kin = <STDIN>;
($a,$b) = split(/,/,$kin);
chomp($a);
chomp($b);
my $aa = $a;
my $bb = $b;
if ($a * $b == 0 ) {
	print "入力値エラー\n";
	exit;
}
if ($a == $b) {
	$g = $a;
	$l = $a;
	goto answer;
}
print "A=$aとB=$bの最大公約数/最小公倍数を求めます。\n";

while ($n != $d){
	if ($a > $b) {
		$d = $a - $b;
		$n = $b;
		$a1 = $n;
		$b1 = $d;
		print "($a,$b)->$a-$b=$d\n";
		$a = $a1;
		$b = $b1
	} else {
		$d = $b - $a;
		$n = $a;
		$a1 = $n;
		$b1 = $d;
		print "($a,$b)->$a-$b=$d\n";
		$a = $a1;
		$b = $b1
	}
}
print "($a,$b)\n";

$g = $n;
$l = $aa*$bb/$n;

answer:

printf "$aaと$bbの\n";

printf "最大公約数:$g\n";

printf "最小公倍数:$aaｘ$bb/$n=$l\n";

リンク