Thinkers'Studio
JavaとC言語の自習ツール
最大公約数を求めるプログラム例(ユークリッドの互除法、再帰呼出し)
 今回は、2つの整数の最大公約数を求めるプログラムです。
 求め方はひとつではありませんが、ここでは「ユークリッドの互除法」と呼ばれる有名なアルゴリズムを使います。
ユークリッドの互除法
 このアルゴリズムは、2つの自然数を対象としたものです。それらを a, b とします( a >= b > 0 )。
   (1) a を b で割り、その余りを r に入れます。
   (2) r が 0 なら b が最大公約数です。処理を終了します。
   (3) そうでないとき、新a = b、新b = r として (1) の手順に戻ります。

最大公約数を求めるプログラム 1 >
 main メソッドで、代入済みの a, b について求めるシンプル版です。
public class Euclid {
    public static void main( String[] args ) {
        int a = 6, b = 3, r;

        //ユークリッドの互除法により最大公約数を求める
        while( (r = a % b) != 0 ) {
            a = b;
            b = r;
        }
        System.out.println( "最大公約数は " + b );
    }
}
 実行結果
最大公約数は 3

最大公約数を求めるプログラム 2 再帰呼出し版 >
 メソッドにするなら、再帰呼出しを使って次のように書くことができます。
 2つの自然数は、キーボードから指定する形にしました。
import java.io.*;
public class Euclid {
    //機 能:ユークリッドの互除法によりa,bの最大公約数を求める
    //戻り値: 最大公約数、(自然数以外が指定されたときは-1)
    static int euclid( int a, int b ) {
        if( a < b ) { int temp = a; a = b; b = temp; } //引数の大小入替
        if( b < 1 ) return -1;                         //0以下は非自然数

        if( a % b == 0 ) return b;
        return euclid( b, a % b );
    }
    public static void main( String[] args ) {
        int a, b, n;

        try {
            BufferedReader br
            = new BufferedReader( new InputStreamReader(System.in) );
            System.out.print( "自然数(1つ目)を指定 : " );
            a = Integer.parseInt( br.readLine() );
            System.out.print( "自然数(2つ目)を指定 : " );
            b = Integer.parseInt( br.readLine() );

            if( (n = euclid( a, b )) > 0 )
                System.out.println( "最大公約数は " + n );
            br.close();
        } catch( Exception e ) {
            System.out.println( "例外が発生しました: " + e );
        }
    }
}

 euclid メソッドの先頭には、大小関係による引数の入替や自然数かどうかのチェックを入れました。
 最大公約数を求める部分は、上の枠内に示したアルゴリズムと同様ですが、割り算の余りを r に入れずに euclid( b, a % b ) のように引数に指定し、自分自身を呼び出しています。  (参考:再帰呼出しとは

 実行結果例2
自然数(1つ目)を指定 : 50
自然数(1つ目)を指定 : 24
最大公約数は 2

(今回のクイズは自習です)
 上記以外の求め方として、最小の公約数でどんどん割っていく方法があります。 筆算で書くとこうです。
    2 | 876  204 
    2 | 438  102 
    3 | 219   51 
         73   17
 73 と 17 はもう割り切れないので、それまで割った数を全部かけて(2×2×3)で12 が最大公約数となります。興味があれば、この処理手順でもプログラムを書いてみてください。
前回のクイズの答え: (前回の問題を見る
   int n = (int)( Math.random() * 6.0 ) + 1;