ユークリッドの互除法のJavaプログラムを2種類紹介

ユークリッドの互除法とは、2つの整数の最大公約数（GCD）を求めるためのアルゴリズムです。このアルゴリズムは、ユークリッドによって紀元前300年ごろに発見されました。

アルゴリズムの手順は以下の通りです：

2つの整数を取り、大きい方をa、小さい方をbとします。
aをbで割り、余りをrとします。(remainderの頭文字)
もしrが0ならば、bが最大公約数となります。
rが0でない場合、bをrで割り、余りを新たなrとします。そして、手順3に戻ります。
この手順を繰り返すことで、最終的に余りが0になった時のbが、2つの整数の最大公約数となります。

例えば、aが24、bが16の場合、以下のように計算されます：

24 ÷ 16 = 1 … 8
16 ÷ 8 = 2 … 0

よって、最大公約数は8となります。

ユークリッドの互除法の図を使った説明

gcd(6,4)=2

gcd(27,12)=gcd(12,3)=3

割り算を使う方法

まずは、互除法の名前の通り割り算を使った方法です。

このプログラムは、二つの正の整数を取り、それらの最大公約数を計算します。

<プログラム>

<実行結果>

最大公約数：12

引き算を使う方法

割り算は引き算でもあるため（6÷2=3は6-2-2-2=0で2を3回引いたら0とでも同じこと）以下のように実装することもできます。

実行結果は上記と同じ。

本記事の内容が、誰かのお役に立ちましたら幸いです。

IT企業向け新人研修おすすめ資料　無料公開中 (saycon.co.jp)