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が最大公約数。
つまり、「割った数」と「あまり」を次の「割られる数」と「割る数」にするということです。割り切れたらそのときの割った数が最大公約数です。
図のように書くとわかりやすいでしょうか
もう少し手間のかかる例のほうが仕組みが見えるかもしれません。
手順を書いてみます。繰り返しは、「割り切れるまで繰り返す(=あまりが0でなければ繰り返す)」いうところでしょう。
2つの整数とあまりを入れる変数を宣言する(a b amari;) 整数(a)に値を代入(a=xx;) 整数(b)に値を代入(b=xx;) あまりを求める(amari) あまり(amari)が0でなければ繰り返す。( { が必要) 割られる数に、割った数を代入。 割った数に、あまりを代入。 あまりを求める(amari) 繰り返しの終わり( }) 割った数を表示する。
while の直前と、} の直前で繰り返し条件をセットしておいて while文 で条件判断をするというのが定番パターンです。青で示しました。
代入の順序は気をつけてください。「割った数に、あまりを代入。」を先にやってしまうと、割った数がわからなくなります。
上記の2つの整数の最大公約数を求めるプログラムを完成させなさい。
検算のために例をあげます。全部を試す必要はありません。いくつか確認してください。最後の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