【Javaで学ぶアルゴリズム】ユークリッドの互除法で最大公約数（GCD）を求める｜自作ロジックとBigInteger活用
取り上げるテーマは、紀元前から伝わる世界最古のアルゴリズムの一つ「ユークリッドの互除法」です。
アルゴリズムの基本概念からJavaでの自作実装、さらには実務で役立つJava標準ライブラリ（BigInteger）を使った一発解決法まで詳しく解説します。
1. ユークリッドの互除法とは？
2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率よく見つけるための定番手法です。
アルゴリズムの定理
2つの整数 $X, Y$ ($X \ge Y$) について、
「$X$ を $Y$ で割った余りを $R$ とすると、$X$ と $Y$ の最大公約数は、$Y$ と $R$ の最大公約数に等しい」
この性質を利用し、余り $R$ が 0 になるまで計算を繰り返すことで、どんなに大きな数字同士でもすばやく最大公約数を導き出すことができます。
2. Javaでの実装例（自作ロジック）
まずは、アルゴリズムの仕組みを理解するために while 文を使って自作してみましょう。
サンプルコード（GCDSample.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$ の場合の計算推移をシミュレーションしてみます。
1071 ÷ 1029 = 1 余り 42
1029 ÷ 42 = 24 余り 21
42 ÷ 21 = 2 余り 0
$\rightarrow$ 余りが 0 になったため、その時の除数 21 が最大公約数！
桁数の大きな数字同士であっても、驚くほど少ないループ回数で答えに辿り着くことができます。
4. 【必見】Java標準ライブラリで一発解決！
アルゴリズムの自作ロジックを理解した上で押さえておきたいのが、Java標準ライブラリ java.math.BigInteger の存在です。
BigInteger.gcd() を使った実装例
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
}
}
【解説と補足ポイント：なぜ標準機能を知っておくべきなのか】
■ 1. 正確性と桁数上限の克服
long 型の範囲を超えるような極めて巨大な数値同士の計算でも、オーバーフローを起こさずに安全に処理できます。■ 2. 堅牢性と最適化
内部で最適化されたアルゴリズムが採用されており、パフォーマンス・信頼性ともに非常に高く設計されています。
■ 3. 実務における「車輪の再発明」の防止
基本ロジックを理解した上で、実務開発では実績のある標準ライブラリを賢く活用するのがプロエンジニアのベストプラクティスです。
5. まとめ
・基本：「$X \div Y$ の余り」を次の除数にするループを回して最大公約数（GCD）を求める。
・応用：最大公約数（GCD）がわかれば、最小公倍数（LCM）は $(X \times Y) \div \text{GCD}$ で計算可能。
・Javaの実務テクニック：BigInteger.gcd()を使えば1行で確実に実装可能。
アルゴリズムの仕組みを知ることはプログラミングの「思考力」を鍛え、便利な標準機能を知ることは「生産性」を高めてくれます。両方のアプローチをバランスよく身につけていきましょう！
PR