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

2023年3月12日 最終更新日時 : 2024年6月25日 山崎講師山崎講師

ユークリッドの互除法とは、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);
    }
}

実行結果は上記と同じ。

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

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

投稿者プロフィール

山崎講師
山崎講師代表取締役
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
対象読者
新入社員
前の記事
エラトステネスの篩のJavaプログラムを紹介
2023年3月12日
次の記事
新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題1をJavaにしてみました
2023年3月17日