最大公約数

2つの整数の最大公約数を求める

2つの整数の最大公約数とは、両方の数をあまりなく割り切れる数のうち一番大きいものです。12と18は両方とも2で割れます。3でも割れます。6でも割れます。一番大きいものは6なので最大公約数は6です。

ユークリッドの互除法

2つの正の整数a,bに対して,最大公約数をもとめることにします。aの方が大きいとします。aをbで割り,余りをrとします。r=0であれば,bが最大公約数です。r>0であれば,b,rを新たなa,bとしてこの操作を再度実行します。 この操作は,繰り返しのたびにbの値が小さくなっていくので,何回かの繰り返しの後,必ず終了します。

たとえば 18と12で、次のようになります。

a=18 b=12とする。
18÷12=1 あまり 6 (r=6)
r=0 でないので、a=12 b=6とする。
12÷6=2 あまり 0 (r=0)
割り切れるので
6が最大公約数。

つまり、「割った数」と「あまり」を次の「割られる数」と「割る数」にするということです。割り切れたらそのときの割った数が最大公約数です。

図のように書くとわかりやすいでしょうか

18と12の公約数

もう少し手間のかかる例のほうが仕組みが見えるかもしれません。

638と572の公約数

計画

手順を書いてみます。繰り返しは、「割り切れるまで繰り返す(=あまりが0でなければ繰り返す)」いうところでしょう。

2つの整数とあまりを入れる変数を宣言する(a b amari;)
整数(a)に値を代入(a=xx;)
整数(b)に値を代入(b=xx;)
あまりを求める(amari)
あまり(amari)が0でなければ繰り返す。( { が必要)
    割られる数に、割った数を代入。
    割った数に、あまりを代入。
    あまりを求める(amari)
繰り返しの終わり( })
割った数を表示する。

while の直前と、} の直前で繰り返し条件をセットしておいて while文 で条件判断をするというのが定番パターンです。青で示しました。

代入の順序は気をつけてください。「割った数に、あまりを代入。」を先にやってしまうと、割った数がわからなくなります。

課題

上記の2つの整数の最大公約数を求めるプログラムを完成させなさい。

ファイル名 Kouyaku.java

検算のために例をあげます。全部を試す必要はありません。いくつか確認してください。最後の2つは間違いではありません。特に注目してください。1は共通の約数がないということです。

 771  909 --- 3 
 615  533 --- 41 
 496  666 --- 2 
 638  572 --- 22 
 306  391 --- 17 
 217  310 --- 31 
 987  893 --- 47 
 946  301 --- 43 
 175  950 --- 25 
 783  841 --- 29 
 610  732 --- 122 
 312  8 --- 8 
 945  734 --- 1 

Javaプログラミング
聖愛中学高等学校
http://www.seiai.ed.jp/
Feb.2009