Javaでユーグリッドの互除法を実装してみた

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

2つの自然数の最大公約数を求めるアルゴリズム。

簡単に表すと

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

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

参考
[ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語](http://mathtrain.jp/euclid)

## 実装してみた

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

そこで、@saka1029 さんからいただいたコメントを反映したコードを新たに記述しました。
@saka1029 さん、ありがとうございました。

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

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

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

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

### 例外処理を行ったコード

``` java
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
```
### その他
「ここおかしいよ」とか「もっとスマートにできるよ」ということがあったら、コメントいただけたら嬉しいです。

## さらに追記(2017年6月23日)
@howdy39 さんのコメントにいただいた通り、微妙な箇所がありました。
@howdy39  さん、ありがとうございました。
@howdy39 さんのご指摘を採用させていただいたスマートなコードがこちら。

例外があった際にreadInput()を再帰的に実行しているので、while文はいりませんでした。

###　実装
``` java 
package com.company;

import java.io.*;

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

    public static void main(String[] args) {
        System.out.println(caution);
        int[] inputs = readInput();
        System.out.println(doEuclideanAlgorithm(inputs[0], inputs[1]));
    }

    private static int[] readInput() {
        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]);
            if (x <= 0 || y <= 0) {
                throw new Exception("");
            }
            return new int[]{x, y};
        } catch (Exception e) {
            System.out.println("入力が不適切です。" + caution);
            return 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
```


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

[ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語](http://mathtrain.jp/euclid)

※ ブログでも同一の投稿をしている
[Javaでユーグリッドの互除法を実装してみた](http://www.sekky0905.com/entry/2017/06/22/Java%E3%81%A7%E3%83%A6%E3%83%BC%E3%82%B0%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95%E3%82%92%E5%AE%9F%E8%A3%85%E3%81%97%E3%81%A6%E3%81%BF%E3%81%9F)