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

Table of Contents

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つの整数についてのものが基本ですが、ここでは複数の整数の最大公約数を計算できるようにしました。

import java.util.*
open class MainKt {
companion object Static {
@JvmStatic
fun main(args: Array<String> = arrayOf()) {
println(
MainKt().solve(
args.toList<String>().
map { it.toLong() } as
MutableList<Long>))
}
}
fun solve(numList: MutableList<Long>): Long {
var newList =
numList.distinct().sorted() as MutableList
var r: Long = 0
while (newList.count() > 1) {
r = newList[0]
newList = newList.
takeLast(newList.count() - 1).map {
it % newList[0]} as MutableList
newList.add(r)
newList = newList.distinct().sorted().
filter { it != 0L } as MutableList<Long>
}
return r
}
}

import java.util.*

open class MainKt {

companion object Static {

@JvmStatic

fun main(args: Array<String> = arrayOf()) {

println(

MainKt().solve(

args.toList<String>().

map { it.toLong() } as

MutableList<Long>))

}

fun solve(numList: MutableList<Long>): Long {

var newList =

numList.distinct().sorted() as MutableList

var r: Long = 0

while (newList.count() > 1) {

r = newList[0]

newList = newList.

takeLast(newList.count() - 1).map {

it % newList[0]} as MutableList

newList.add(r)

newList = newList.distinct().sorted().

filter { it != 0L } as MutableList<Long>

}

return r

}

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

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

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

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

使い方

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

例

java -jar Jar.jar 82 48 36 72
# => 2

1 2	java -jar Jar.jar 82 48 36 72 # => 2

活用

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

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

data class Fraction(
var denominator: Long, var numerator: Long) {
init {
var r = MainKt().solve(
mutableListOf(denominator, numerator))
denominator /= r
numerator /= r
}
}

data class Fraction(

var denominator: Long, var numerator: Long) {

init {

var r = MainKt().solve(

mutableListOf(denominator, numerator))

denominator /= r

numerator /= r

}

この記事を見た人は次の記事も見ています

(English) NodeJS: innerHTML with xmldom

The Life