ユーグリッドの互除法とは
2つの自然数の最大公約数を求めるアルゴリズム。
簡単に表すと
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日)
上記のコードは、もともと入力などについては深く考えず、ただアルゴリズムを実装してみたというものだったので、例外処理などを考慮しておらず、簡単に落ちます。
そこで、@saka1029 さんからいただいたコメントを反映したコードを新たに記述しました。
@saka1029 さん、ありがとうございました。
今回は、以下のような条件でコードを記述しています。
ユークリッドの互除法の実装なら負の数は入り口ではじく。
数字以外のものの入力がされても、落ちない
また、自然数に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
その他
「ここおかしいよ」とか「もっとスマートにできるよ」ということがあったら、コメントいただけたら嬉しいです。
さらに追記(2017年6月23日)
@howdy39 さんのコメントにいただいた通り、微妙な箇所がありました。
@howdy39 さん、ありがとうございました。
@howdy39 さんのご指摘を採用させていただいたスマートなコードがこちら。
例外があった際にreadInput()を再帰的に実行しているので、while文はいりませんでした。
実装
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
参考にさせていただいたサイト
ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語
※ ブログでも同一の投稿をしている
Javaでユーグリッドの互除法を実装してみた