🎯

【Java】ユークリッドの互除法

に公開
Java
初心者
tech

ユークリッドの互除法

ユークリッドの互除法とは、2つの整数の最大公約数を効率的に求めるアルゴリズムです。

ユークリッドの互除法の手順

  1. 2つの整数aとbがあります。
  2. 大きい方の値を小さい方の値で割り、その余りをrとします。
  3. 大きい方の値をrで置き換えます。
  4. 2.と3.を再帰的に繰り返し、余りが0になるまで繰り返します。
  5. 余りが0になった時の大きな値が最大公約数になります。

例 a=210、b=924の場合

  1. (210, 924)
  2. 924 ÷ 210 の余りは、84
  3. (210, 84)
  4. 210 ÷ 84 の余りは、42
  5. (42, 84)
  6. 84 ÷ 42 の余りは、0
  7. (42, 0) ∴最大公約数は、42

ユークリッドの互除法のコード例

public class Main {
    static int calcGcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return calcGcd(b, a % b);
        }
    }
    
    public static void main(String[] args) {
        int a = 60;
        int b = 48;
        int gcd = calcGcd(a, b);
        System.out.println(a + " と " + b + " の最大公約数は " + gcd);
    }
}

コード例の解説

calcGcdメソッドのみ解説します。

  1. 仮引数a=60とb=48が渡され、calcGcdメソッドを実行します。
  2. if文の条件式のb == 0を満たさないので、
  3. elseにより、実引数としてb=48と60 ÷ 48 の余り 12を渡してcalcGcdメソッドの再帰呼び出しを行います。
  4. 仮引数a=48とb=12が渡され、calcGcdメソッドを実行します。
  5. if文の条件式のb == 0を満たさないので、
  6. elseにより、実引数としてb=48と48 ÷ 12 の余り 0を渡してcalcGcdメソッドの再帰呼び出しを行います。
  7. 仮引数a=12とb=0が渡され、calcGcdメソッドを実行します。
  8. if文の条件式のb == 0を満たすので、
  9. 返り値としてa=12を返します。

3つ以上の整数の最大公約数を効率的に求めるコード例

public class Main {
    static int calcGcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return calcGcd(b, a % b);
        }
    }
    
    static int calcGcd(int[] a) {
        int gcd = a[0];
        
        for (int i = 1; i < a.length; i++) {
            gcd = calcGcd(gcd, a[i]);
        }
        
        return gcd;
    }
    
    public static void main(String[] args) {
        int[] a = {12, 30, 42};
        int gcd = calcGcd(a);
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println("の最大公約数は " + gcd);
    }
}

コード例の解説

標準出力に出力するコードの解説は割愛します。
また、int型のaとbを受け取るcalcGcdメソッドは、ユークリッドの互除法のコード例で解説済みですので、途中経過を省略した解説を行います。
そして、このコードはオーバーロードを使用しています。オーバーロードについては、下記を参考にしてください。

https://zenn.dev/goriki/articles/005-about-methods

  1. mainメソッドで、配列aを{12, 30, 42}で初期化します。
  2. 実引数として配列aを渡して、calcGcdメソッドを呼び出します。
  3. 仮引数として配列aを受け取り、calcGcdメソッドを実行します。
  4. 変数gcdにa[0]=12を代入します。
  5. 2回ループするfor文を定義します。
  6. 実引数としてgcd=12とa[1]=30を渡して、calcGcdメソッドを呼び出します。
  7. 仮引数としてa=12とb=30を受け取り、ユークリッドの互除法を行うcalcGcdメソッドを実行します。
  8. 途中の過程は省略しますが、a=12とb=30の最大公約数6を返り値として戻します。
  9. for文の2回目のループとして、実引数としてgcd=6とa[2]=42を渡して、calcGcdメソッドを呼び出します。
  10. 途中の過程は省略しますが、a=6とb=42の最大公約数6を返り値として戻します。
  11. 変数gcdを6に更新します。
  12. 返り値として変数gcd=6を戻します。

Discussion