このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*目次 [#r6d513eb]

#contents


*はじめに [#p311f8a1]

 2つの整数の最大公約数(GCM)を求めるもっとも素朴な方法は、2,3,5,…とmin(a,b)以内の素数について割っていくことである。割った結果、2つの整数が割り切れれば、その公約数にはその素数が含まれるということを意味する。つまり、最大公約数はこうした素数のすべての掛け合わせたものである。このアルゴリズムは次の通りである。

-Input:A,B(10進数の整数)
-Output:GCM(AとBの最大公約数)

#code(){{
GCM=1
if min(a,b)≦2 then
	exit
while 2|a ∧ 2|b do
	a = a/2
	b = b/2
	GCM = GCM*2
if min(a,b)≦3 then
	exit
while 3|a ∧ 3|b do
	a = a/3
	b = b/3
	GCM = GCM*3
if min(a,b)≦5 then
	exit
while 5|a ∧ 5|b do
	a = a/5
	b = b/5
	GCM = GCM*5
…(min(a,b)以下の素数についてすべて同様に考える)…

}}

 ところが、このアルゴリズムでは、min(a,b)以下のすべての素数のリストを用意しておかなければならない。これを解決するアルゴリズムのひとつがユークリッドの互除法である。


*ユークリッドの互除法 [#w5240c54]

 ユークリッドの互除法では、素数を用意せずとも、どんな数の最大公約数でも求めることができる。2,000年以上前に[[ユークリッド]]によって発見されたアルゴリズムである。もっとも基本的なアルゴリズムともいえる。

 ユークリッドの互除法のアルゴリズムは次の通りである。

-Input:a,b(0以上の整数)
-Output:(a,b)(aとbの最大公約数)

#code(){{
r[-2]←a,r[-1]←b,n←0
if r[n-1]=0 then
	output r[n-2]
	return
else
	r[n]←r[n-2]%r[n-1]
	n←n+1
	goto 2行目


}}

例:a=21,b=14の最大公約数(a,b)をユークリッドの互除法を使って求める。

-n:カウンターのn
-qSUB{n};:rSUB{n-2};÷rSUB{n-1}の余り

|LEFT:''n''|LEFT:''qn''|LEFT:''rn''|
|RIGHT:-2|RIGHT:|BGCOLOR(#FFFF00):RIGHT:21|
|RIGHT:-1|RIGHT:|BGCOLOR(#FFFF00):RIGHT:14|
|RIGHT:0|RIGHT:1|BGCOLOR(#FF0000):RIGHT:7|
|RIGHT:1|RIGHT:2|BGCOLOR(#00CCFF):RIGHT:0|
|RIGHT:2|RIGHT:|RIGHT:|

 黄色の部分が初期値の入力である。出力結果は、水色のように0となった個所のひとつ上である。よって、赤色が最大公約数であり、これが出力される。

(21,14)=7

 このように素因数分解をせずに単に割り算をするだけで、最大公約数が求められるわけである。

**Javaによる実装 [#n2dcccbc]

#code(java){{
/*
 * ユークリッドの互除法で最大公約数(GCM)と最小公約数(LCM)を求める
 * 入力:2つの整数
 * 出力:最大公約数
 */
import java.io.*;
public class EuclidGCM {

	public static void main(String[] args){
		int a=0,b=0;
		
		//整数を入力する
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			try{
				String line;
			
				System.out.println("整数a:");
				line=rd.readLine();
				a=Integer.parseInt(line);
			
				System.out.println("整数b:");
				line=rd.readLine();
				b=Integer.parseInt(line);		
			}catch(IOException e){
				System.out.println("入力エラー");
				return;
			}catch(NumberFormatException e){
				System.out.println("整数を入力してください。");
				continue;
			}
		
			//aまたはbが0なら終了する
			if(a==0 || b==0){
				break;
			}
		
			//aとbを保存しておく。
			int sa=a,sb=b;
			//割り切れるまで繰り返す。
			while(b != 0){
				int r = a%b;
				a=b;
				b=r;
			}
			
			//最小公約数を求める
			int lcm = sa * sb / a;
		
			//最大公約数を表示する。
			System.out.println(sa + "と" + sb + "の最大公約数は" + a + "です。");
			//最小公約数を表示する。
			System.out.println(sa + "と" + sb + "の最小公約数は" + lcm + "です。");
			
		}
	}
}

}}


*ユークリッドの互除法における繰り返し回数 [#rc2daad0]

 ユークリッドの互除法を求めるときの表に着眼する。qSUB{n};の列がすべて1になるとき、即ち「∀n;qSUB{n};=1」のとき、繰り返し回数が一番多い。そのときの式は次のようになる。

&mimetex("r_{n-2} = r_{n-1} + r_n");

 これはちょうどフィボナッチ数を定義する漸化式を逆順にしたものになっている。よって、互除法における繰り返し回数(lとする)の上限は次の不等式によって表される。ここで&mimetex("\theta = \frac{1 + \sqrt{5}}{2}");とする(このθは[[黄金比]]である((1:θ=θ:1-θを満たす)))。

&mimetex("l");~
&mimetex("< \frac{\log b}{\log \theta} + 1");~
&mimetex("< 1.4 \log b +1");

 よって、繰り返し回数lはbの桁数程度ということを意味する。


*参考文献 [#n9894b1b]

-講義ノート
-『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』