Perlでユークリッドの互助法を用いる。

開発環境はWindows 7 Professional(32bit)+Perl 5.24.0。

ユークリッドの互助法とは、2つの自然数の最大公約数を求めるアルゴリズムです。

aとbの2つの自然数があって(a≧b)、aをbで割り、出現した余りをxとします。今度は、bをxで割り、出現した余りをx´とします。そして、今度は、xをx´で割り、出現した余りをx´´とします。これを、2つの数が割り切れるまで繰り返して、その時の「わる数」の部分が2つの自然数の最大公約数となります。

use strict;
use warnings;

my $a = 42;
my $b = 30;

print(ea($a,$b));


sub ea{
	my ($a,$b) = @_;

	my $dummy = 0;

　　　　# $bの方が数値が大きい場合は入れ替える
	if($a < $b){
		$dummy = $b;
		$b = $a;
		$a = $dummy;
	}

		while($a % $b != 0){
			$dummy = $a % $b;
			$a = $b;
			$b = $dummy;
		}

	return $b;
}

上記の場合、42と30の最大公約数は6なので、結果は6と表示されます。最初、returnするのを$aと書いていたので、12が表示されて、おかしいな？と思い、$bをreturnすると6と表示されたので、こっちかと修正しました。

もし、同じ自然数だった場合は、その数が最大公約数となります。例えば、42同士だったら、42が最大公約数です。