【Javaで学ぶアルゴリズム】ユークリッドの互除法で最大公約数を求め

前回の記事では Arrays.sort() を使った並び替えを学びましたが、今回は一歩進んで、有名な数学的アルゴリズムを自分の手で実装してみましょう。

取り上げるテーマは、紀元前から伝わる世界最古のアルゴリズムの一つ「ユークリッドの互除法」です。

1. ユークリッドの互除法とは？

2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率よく見つけるための手法です。

アルゴリズムの定理

2つの整数 X, Y (X ≧ Y) について、

「X を Yで割った余りを Rとすると、XとY の最大公約数は、YとRの最大公約数に等しい」

 

この性質を利用し、余り R が 0$になるまで計算を繰り返すことで、どんなに大きな数字同士でも最大公約数を導き出すことができます。

---

2. Javaでの実装例（自作ロジック）

まずは、アルゴリズムの仕組みを理解するために、while 文を使って自作してみましょう。

Java

public class GCDSample {
    public static void main(String[] args) {
        int x = 1071;
        int y = 1029;
        
        int result = getGcd(x, y);
        System.out.println(x + " と " + y + " の最大公約数は " + result + " です。");
    }

    // 最大公約数を求めるメソッド
    public static int getGcd(int x, int y) {
        // R = 0 となるまで、YとRを変えながらループ
        while (y != 0) {
            int r = x % y; // 剰余Rを求める
            x = y;         // 次の計算のためにYをXに代入
            y = r;         // 次の計算のためにRをYに代入
        }
        return x; // 余りが0になった時の除数が最大公約数
    }
}

---

3. アルゴリズムの挙動を追う

例として、X = 1071, Y = 1029 の場合をシミュレーションしてみます。

1. 1071 ÷ 1029 = 1 余り 42

2. 1029 ÷ 42 = 24 余り 21

3. 42 ÷ 21 = 2 余り 0

4. 余りが 0 になったので、その時の除数 21が最大公約数！

大きな数字でも、驚くほど少ない回数で答えに辿り着けます。

---

4. 【必見】Java標準ライブラリで一発解決！

ここまでロジックを解説してきましたが、実はJavaの標準ライブラリ java.math.BigInteger を使うと、自作する必要すらありません。

Java

import java.math.BigInteger;

public class GCDMain {
    public static void main(String[] args) {
        // valueOfを使用してBigIntegerインスタンスを作成
        BigInteger b1 = BigInteger.valueOf(1071);
        BigInteger b2 = BigInteger.valueOf(1029);
        
        // gcdメソッドを呼び出すだけ
        BigInteger gcd = b1.gcd(b2);
        
        System.out.println("最大公約数は: " + gcd); // 実行結果: 21
    }
}

なぜこれを知っておくべきか

• 正確性: long 型を超えるような巨大な数値でも計算可能です。

• 堅牢性: 内部で最適化されたアルゴリズムが採用されており、信頼性が高いです。

• 実務の知恵: ロジックを理解した上で、実務では「車輪の再発明」を避け、標準機能を賢く使うのがプロの技術です。

---

5. まとめ

• 基本: 「X ÷ Yの余り」を次の除数にするループを回す。

• 応用: 最大公約数（GCD）がわかれば、最小公倍数（LCM）は (X × Y) ÷ GCD$ で求まる。

• Javaの凄さ: BigInteger.gcd() を使えば一瞬で実装完了。

アルゴリズムの仕組みを知ることは、プログラミングの「思考力」を鍛えてくれます。一方で、便利な標準機能を知ることは「生産性」を高めてくれます。

両方の能力を鍛えたいものです。