すずろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

スポンサーリンク

Kotlin 最大公約数(GCD)を求めるプログラムを作成してみた!

f:id:Suzushin:20170429140030j:plain

こんばんは、すずしんです。

今日は、Kotlinのプログラミングをしてみました。
今回作成したプログラムは、ユークリッドの互除法最大公約数(GCD)を求めるというものです。
Kotlinのプログラミングは、なかなか楽しいです。

最大公約数(GCD)とは?

最大公約数というのは、共通する約数の中で一番大きな数のことを言います。
最大公約数は、英語で「Greatest Common Divisor」と言います。
略してGCDですね!

最大公約数の例を挙げてみます。
例えば、16と24の最大公約数の基本的な求め方では以下のように行います。

16の約数: 1, 2, 4, 8, 16
24の約数: 1, 2, 3, 4, 6, 8, 12, 24
16と24の最大公約数: 8

ユークリッドの互除法とは?

ユークリッドの互除法と言うのは、2つの自然数の最大公約数を求めるアルゴリズムの1つです。
2つの自然数a,b(a ≧ b)において、aのbによる剰余をrとした時、aとbの最大公約数はbとrとの最大公約数に等しいという性質が成り立ちます。
この性質を利用して、bをrで割った剰余、除数rをその剰余で割った剰余、と剰余を求める計算を繰り返し、剰余が0になった時の除数がaとbとの最大公約数となります。

最大公約数を求める関数をgcd(a, b)として、先ほどの例であげた16と24の最大公約数を求める例を見てみます。

gcd(24, 16) = gcd(16, 8) = gcd(8, 0) = 8

いかがでしょうか?
かなりシンプルに最大公約数を求めることができますよね。

Kotlinで最大公約数(GCD)を求めるプログラム

それでは本題です。
以上の事を踏まえて、Kotlinで2つの数a,bの最大公約数(GCD)を求めるプログラムを作成してみました。
それが以下のプログラムです。

import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val a = scanner.nextInt()
    val b = scanner.nextInt()
    scanner.close()
    println(String.format("gcd(%d, %d) = %d%n", a, b, gcd(a, b)))
}

fun gcd(a: Int, b: Int): Int {
    if(a < b) return gcd(b, a)
    if(b == 0) return a
    return gcd(b, a % b)
}

main関数では、まずScannerを用意して標準入力を受け付けるようにします。
そして、nextInt()を使って2つの数字を取得します。
最後に、それらの最大公約数をgcd()で求めて結果を出力しています。

gcd関数では、最初のif文でaとbの大きさの比較をしています。
その後、剰余bが0になっていたら、最大公約数はaなのでaの値を返します。
そうでなければ、剰余r = a % bとして、gcd(b, r)を計算します。
再起呼び出しなので、bが0になるまで繰り返し計算されます。

プログラム自体は、どちらも非常にシンプルですよね。

プログラムの実行結果

上記プログラムを実行した結果の例は以下の通りです。
ここでも、16と24の最大公約数を求めてみました。
確かに、最大公約数が8となっていて、正しい値になっていることが分かりますね。

16 24
gcd(16, 24) = 8

ひとこと

今回の記事では、Kotlinでユークリッドの互除法を使った最大公約数(GCD)を求めるプログラムを作成しました。
ユークリッドの互除法のアルゴリズムが理解できれば、実装は非常に簡単ですね。
比較的サクッとプログラムを書くことができました。

こうしたプログラムを書くことは、プログラミングにおいて良い練習になると思います。
あなたも得意なプログラミング言語で、最大公約数(GCD)を求めてみてはいかがでしょうか?

追記

Kotlinでは、gcd(a, b)を以下のように書くこともできます。
参考までにどうぞ。

fun gcd(a: Int, b: Int): Int = if(a < b) gcd(b, a) else if(b == 0) a else gcd(b, a % b)