【技術記事】Javaでユーグリッドの互除法を実装してみた

ユーグリッドの互除法とは

簡単に表すと

a % b = r
b % r = s
r % s = 0

といった形で、割る数を次の割られる数、余りを次の割る数にして再帰的にそれを繰り返して行く。
余りが0になった時の割る数(上の例だとs)が自然数aとbの最大公約数になる。

参考
ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

実装してみた

package com.company;

import java.io.*;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String[] str = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);

            System.out.println(getCommonDivisor(x, y));

        } catch (Exception e) {
            System.out.println(e);
        }
    }

    private static int getCommonDivisor(int x, int y) {
        int biggerNum = Math.max(x, y);
        int smallerNum = Math.min(x, y);

        // 大きい方から小さい方を割った余を求める
        int surplus = biggerNum % smallerNum;

        // 割り切れていれば、それを返す
        if (surplus == 0) {
            return smallerNum;
        }
        // 割り切れなければ再帰的に自信を呼び出す
        surplus = getCommonDivisor(smallerNum, surplus);

        return surplus;
    }
}

試してみる

// 入力
390 273 

// 出力
39

追記(2017年6月23日)

上記のコードは、もともと入力などについては深く考えず、ただアルゴリズムを実装してみたというものだったので、例外処理などを考慮しておらず、簡単に落ちます。

Qiita の方で、その点をご指摘いただきました。
そこで、いただいたコメントを反映したコードを新たに記述しました。

今回は、以下のような条件でコードを記述しています。

ユークリッドの互除法の実装なら負の数は入り口ではじく。

数字以外のものの入力がされても、落ちない

また、自然数に0を含める流派と自然数に0を含めない流派が存在しますが、今回は、「自然数に0を含めない流派」を採用します。

例外処理を行ったコード

package com.company;

import java.io.*;

class Main {
    private static int x = -1;
    private static int y = -1;
    private static final String caution = "自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)";

    public static void main(String[] args) {
        System.out.println(caution);
        readInput();
        System.out.println(doEuclideanAlgorithm(x, y));
    }

    private static void readInput() {
        try {
            while (x <= 0 || y <= 0) {
                BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
                String[] str = bufferedReader.readLine().split(" ");
                x = Integer.parseInt(str[0]);
                y = Integer.parseInt(str[1]);
                if (x <= 0 || y <= 0) {
                    System.out.println("入力が不適切です。" + caution);
                }
            }
        } catch (Exception e) {
            System.out.println("入力が不適切です。" + caution);
            readInput();
        }
    }

    private static int doEuclideanAlgorithm(int x, int y) {
        int biggerNum = Math.max(x, y);
        int smallerNum = Math.min(x, y);

        // 大きい方から小さい方を割った余を求める
        int surplus = biggerNum % smallerNum;

        // 割り切れていれば、それを返す
        if (surplus == 0) {
            return smallerNum;
        }
        // 割り切れなければ再帰的に自信を呼び出す
        surplus = doEuclideanAlgorithm(smallerNum, surplus);

        return surplus;
    }
}

試してみた

自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
a a
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 0
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
0 273 
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
-390 273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 -273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 273 
39

参考にさせていただいたサイト

ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

※ Qiitaでも同一の投稿をしている
Javaでユーグリッドの互除法を実装してみた - Qiita