note002:最大公約数と最小公倍数

2013年1月14日

 小学校高学年で分数を習うけれど、分子、分母の桁が大きいとき、「約分」の方法って悩まなかった? 爺は直感的に分子、分母を同じ数で割って、それなりに小さい数になれば、それでよし!としていた。でも、例えば「239/929を約分せよ!」とゆー問題だったらどうだろう。下一桁が9なので、直感的に約分可能なのは、3か9、あるいは(7×7=49)なので、7も考えられる。この問題は意地悪で分子も分母も素数なので、これ以上約分できない。でも、どーやったら、これ以上約分できないと言えるの? それが2つの値の最大公約数を求めるとゆーことなのら。

値(1)
値(2)

 ふたつの数の最大公約数(Greatest Common Divisor)を求めるには、「ユークリッドの互除法」という超有名な方法(アルゴリズム)がある。その方法とは、例えば、gcd(123,45)の場合、123を45で割ってその余りを求める。もし、余りが「0」ならば、45が最大公約数なのだが、「123%45」は「33」だ。次は「除数%剰余」として、つまり「gcd(45,33)」として、「45%33」を実行。余りが「12」なので→「33%12=9」→「12%9=3」→「9%3=0」、余りが「0」になったので、除数「3」が123と45の最大公約数となる。gcd関数の中でgcd関数を呼び出していることに注目。これを「再帰的呼び出し」、あるいは「再帰関数」と言う。最小公倍数(Least Common Multiple)の求め方は、ふたつの数を掛け合わせ、それを最大公約数で割ればよい。

JavaScript

<script>
function myCalc(select){
	var m = document.myFORM.myValue1.value;
	var n = document.myFORM.myValue2.value;
	if(isNaN(m)||isNaN(n)){
		alert("数値ではありません!");
	}else{
		switch(select){
			case 0:	ans1 = gcd(m,n);
				document.getElementById("result1").value = ans1;
			break;
			case 1: ans2 = lcm(m,n);
				document.getElementById("result2").value = ans2;
			break;
		}
	}
	function gcd(m,n){
		var r = m % n;
		if (r == 0) return n;
		return gcd(n, r);
	}
	function lcm(m,n){
		var r = Math.abs(m*n)/gcd(m,n);
		return r;
	}
}
</script>

HTML

<form name="myFORM">
値(1)<input type="text" size="8" name="myValue1" value="123">
<input type="button" value=" 最大公約数 " onclick="myCalc(0)">
<input type="text" size="8" id="result1" value="0"><br />
値(2)<input type="text" size="8" name="myValue2" value="45">
<input type="button" value=" 最小公倍数 " onclick="myCalc(1)">
<input type="text" size="8" id="result2" value="0">
</form>

※参考:「C言語によるアルゴリズム事典」(奥村晴彦/著) ※爺註:「m % n」とする際、「m > n」になっていることが前提条件なのだが、例えば、gcd(45,123)を実行すると、「45%123=45」となり、次に再帰呼び出しをする際には、「gcd(除数,剰余)」なので、ちゃんと「gcd(123,45)」になっちゃうところが、アルゴリズム的には、おもしろい。ってゆーか、先人たちの考えたアルゴリズムは完璧なまでに洗練されていて、「うまいことできてるなぁ!」と爺は感心するばかり^^;