Kotlin: ユークリッドの互除法で最大公約数を求める


Kotlinユークリッドの互除法を書いてみました。

ユークリッドの互除法

2つの自然数の最大公約数を求める方法のひとつ。 ユークリッドの原論に記述があります。

Example

46 と 36 の最大公約数をユークリッドの互除法で求めてみます。

\begin{eqnarray}
46 & = & 36 \times 1 + 10 \\
36 & = & 10 \times 3 + 6 \\
10 & = & 6 \times 1 + 4 \\
6 & = & 4 \times 1 + 2 \\
4 & = & 2 \times 2
\end{eqnarray}

これより最大公約数は 2 となります。

環境

  • Kotlin 1.0.0

コード

ユークリッドの互除法は2つの整数についてのものが基本ですが、ここでは複数の整数の最大公約数を計算できるようにしました。

main関数は solve を呼び出します。 計算をやっているのは solve です。

solve最大公約数を求めたい自然数のリストを渡して、 solveが最大公約数を返します。 main はその値を標準出力に出力しています。

最大公約数がない場合(共通因数がない場合)は1を返します。

きっともっと効率のいいやり方があると思います。

使い方

jar を作って実行する場合は、 次のようにします。

活用

最大公約数が求められますから、分数の約分をすることができます。

クラスの分け方はきれいではないですが、 例えば次のように 分数のクラス Fraction を作ります。 初期化処理のところで分母と分子を最大公約数で割って既約分数にしています。 もし 分母(numerator) が 1 になれば整数です。