【Java】2つの数値の最大公約数（GCD）を求めるプログラムの書き方

この記事では、Javaで2つの数値の最大公約数（GCD：Greatest Common Divisor）を求める方法について解説します。最大公約数とは、2つの数値をどちらも余りなく割り切ることができる最大の整数のことです。

GCDの求め方：実行例

以下に具体的な実行例を示します。

入力

入力値が次のとおりであるとします。

値1 : 18
値2 : 24

出力

期待される出力は次のとおりです。

2つの数値のGCD : 6

アルゴリズム

GCDを求める基本的な手順は以下のとおりです。

ステップ1 - 開始
ステップ2 - 3つの整数変数 input_1、input_2、gcd を宣言する
ステップ3 - ユーザーに2つの整数値の入力を促す（または整数値をハードコードする）
ステップ4 - 値を読み込む
ステップ5 - 各数値iが2つの数（input_1とinput_2）をどちらも完全に割り切れるか確認し、割り切れた場合はその値を変数に格納する
ステップ6 - 最終的な「i」の値を2つの数値のGCDとして表示する
ステップ7 - 終了

例1：ユーザー入力から求める場合

ここでは、Scannerクラスを使ってユーザーからの入力を受け付け、その値をもとにGCDを計算して表示します。

import java.util.Scanner;
public class GCD{
   public static void main(String[] args){
      int input_1 , input_2 , gcd ;
      Scanner reader = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter a first number: ");
      input_1 = reader.nextInt();
      System.out.print("Enter a second number: ");
      input_2 = reader.nextInt();
      gcd = 1;
      for(int i = 1; i <= input_1 && i <= input_2; i++){
         if(input_1%i==0 && input_2%i==0)
         gcd = i;
      }
      System.out.printf("\nThe GCD of %d and %d is: %d", input_1, input_2, gcd);
   }
}

出力

A reader object has been defined
Enter a first number: 24
Enter a second number: 18
The GCD of 24 and 18 is: 6

例2：値を事前に定義しておく場合

ここでは、整数値があらかじめプログラム内で定義されており、その値を使用してGCDを計算し、コンソールに結果を出力します。

public class GCD{
   public static void main(String[] args){
      int input_1 , input_2 , gcd ;
      input_1 = 12;
      input_2 = 18;
      gcd = 1;
      System.out.print("The first number is " + input_1);
      System.out.print("\nThe second number is " + input_2);
      for(int i = 1; i <= input_1 && i <= input_2; i++){
         if(input_1%i==0 && input_2%i==0)
         gcd = i;
      }
      System.out.printf("\nThe GCD of %d and %d is: %d", input_1, input_2, gcd);
   }
}

出力

The first number is 12
The second number is 18
The GCD of 12 and 18 is: 6

補足：ユークリッドの互除法による効率的な計算

上記の例では1から順に全ての数を試す「全探索」のアプローチを用いていますが、より効率的にGCDを求めたい場合はユークリッドの互除法を利用するのがおすすめです。これは「大きい方の数を小さい方の数で割り、その余りと小さい方の数に対して同じ操作を繰り返す」という手法で、余りが0になったときのもう一方の数がGCDとなります。特に大きな数同士のGCDを求める場合、ループ回数が大幅に減るため高速に処理できます。