【Java】2つ以上の数値や配列の最大公約数（GCD）を求めるプログラム

最大公約数（GCD：Greatest Common Divisor）とは、複数の整数に共通する約数の中で最も大きいもののことです。この記事では、2つ以上の数値（配列の全要素）からGCDを求めるJavaプログラムを、サンプルコードと実行結果とあわせて解説します。

サンプルコード

public class Demo{
    static int gcd_of_nums(int val_1, int val_2){
        if (val_1 == 0)
            return val_2;
        return gcd_of_nums(val_2 % val_1, val_1);
    }
    static int find_gcd(int arr[], int no){
        int result = arr[0];
        for (int i = 1; i < no; i++){
            result = gcd_of_nums(arr[i], result);
            if(result == 1){
                return 1;
            }
        }
        return result;
    }
    public static void main(String[] args){
        int my_arr[] = { 7, 49, 177, 105, 119, 42};
        int no = my_arr.length;
        System.out.println("配列の要素のGCDは");
        System.out.println(find_gcd(my_arr, no));
    }
}

実行結果

配列の要素のGCDは
1

プログラムの解説

1. gcd_of_numsメソッド ― ユークリッドの互除法で2数のGCDを計算

Demoクラスには、2つの整数を受け取ってGCDを返すstaticメソッド「gcd_of_nums」が定義されています。第1引数が0であれば第2引数をそのまま返し、そうでなければ「val_2 % val_1」と「val_1」を新しい引数として自分自身を再帰呼び出しします。これはユークリッドの互除法と呼ばれる古典的なアルゴリズムで、剰余を繰り返し求めることで効率よくGCDを導き出せます。

2. find_gcdメソッド ― 配列全体のGCDを順次計算

次に、配列とその要素数を引数に取るstaticメソッド「find_gcd」が定義されています。まず配列の先頭要素を変数「result」に代入し、forループで2番目以降の要素を1つずつ取り出しては、直前の「result」とのGCDを計算して上書きしていきます。

途中で「result」が1になった場合、1より小さい正の約数は存在しないため、それ以上計算しても結果は変わりません。そこで即座に1を返すことで、残りのループ処理を省略しています（早期リターンによる最適化です）。ループを最後まで回りきれば、配列全体のGCDが「result」に格納された状態で返却されます。

3. mainメソッド ― 配列の定義と結果の出力

mainメソッドでは、整数型の配列「my_arr」を定義し、lengthプロパティでその要素数を取得します。その後、配列と要素数を引数としてfind_gcdメソッドを呼び出し、計算結果をコンソールに出力します。

サンプルの配列 {7, 49, 177, 105, 119, 42} の場合、7は49・105・119・42を割り切れますが、177（= 3 × 59）は割り切れません。したがって、全要素に共通する約数は1のみとなり、実行結果も「1」と表示されます。

ポイントまとめ

• 2つの数値のGCDは、ユークリッドの互除法を再帰で実装すると簡潔に書ける
• 配列のGCDは「先頭要素を起点に、隣接要素とのGCDを順次更新する」方式で求められる
• 途中でGCDが1になったら早期リターンすることで、無駄な計算を回避できる