ユークリッドの互除法のJavaプログラムを2種類紹介
山崎講師ユークリッドの互除法とは、2つの整数の最大公約数（GCD）を求めるためのアルゴリズムです。このアルゴリズムは、ユークリッドによって紀元前300年ごろに発見されました。
アルゴリズムの手順は以下の通りです：
2つの整数を取り、大きい方をa、小さい方をbとします。
aをbで割り、余りをrとします。(remainderの頭文字)
もしrが0ならば、bが最大公約数となります。
rが0でない場合、bをrで割り、余りを新たなrとします。そして、手順3に戻ります。
この手順を繰り返すことで、最終的に余りが0になった時のbが、2つの整数の最大公約数となります。
gcd(a , b) = gcd(b , r)
例えば、aが24、bが16の場合、以下のように計算されます：
24 ÷ 16 = 1 … 8
16 ÷ 8 = 2 … 0
よって、最大公約数は8となります。
ユークリッドの互除法の図を使った説明
| gcd(6,4)=2 |
| gcd(27,12)=gcd(12,3)=3 |
例題1
gcd(884,323)を求めよ。
割り算を使う方法
まずは、互除法の名前の通り割り算を使った方法です。
このプログラムは、二つの正の整数を取り、それらの最大公約数を計算します。
<プログラム>
public class EuclidAlgorithm {
public static int findGCD(int num1, int num2) {
// num2が0になるまで繰り返す
while (num2 != 0) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
public static void main(String[] args) {
int num1 = 60;
int num2 = 24;
int gcd = findGCD(num1, num2);
System.out.println("最大公約数：" + gcd);
}
}<実行結果>
| 最大公約数：12 |
引き算を使う方法
割り算は引き算でもあるため（例えば、6÷2=3は6-2-2-2=0で2を3回引いたら0とでも同じこと）以下のように実装することもできます。
package experiments;
public class SubtractionEuclidAlgorithm {
public static int findGCD(int num1, int num2) {
while (num1 != num2) {
if (num1 > num2) {
num1 = num1 - num2;
} else {
num2 = num2 - num1;
}
}
return num1;
}
public static void main(String[] args) {
int num1 = 60;
int num2 = 24;
int gcd = findGCD(num1, num2);
System.out.println("最大公約数：" + gcd);
}
}実行結果は上記と同じ。
本記事の内容が、誰かのお役に立ちましたら幸いです。
