すずろぐ

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

スポンサーリンク

Kotlin 最小公倍数(LCM)を求めるプログラムを作成してみた!

f:id:Suzushin:20170429140030j:plain

おはようございます、すずしんです。

前回の記事では、Kotlinでユークリッドの互除法を使って、最大公約数(GCD)を求めるプログラムを作成してみました。

www.suzushin7.jp

最大公約数(GCD)を求めたら…。
次にやりたくなるのは、最小公倍数(LCM)ですよね?
というわけで、今回はKotlinで最小公倍数(LCM)を求めるプログラムを作成してみました。

最小公倍数(LCM)とは?

最小公倍数というのは、 2つ以上の正の整数の共通な倍数(公倍数)のうち、最小のものを最小公倍数といいます。
英語で言うと「Least Common Multiple」となります。
略してLCMですね!

簡単な最小公倍数(LCM)の例を挙げてみます。
16と24の最小公倍数(LCM)の求め方として、基本的な方法では以下のように行います。

16の倍数: 16, 32, 48, 64, ...
24の倍数: 24, 48, 72, 96, ...
16と24の最小公倍数: 48

ですが、ここでは最小公倍数(LCM)を最大公約数(GCD)を使って求めてみます。
すると、最小公倍数(LCM)は以下のように求めることができます。

LCM(a, b) = (a * b) / GCD(a, b)

つまり、2つの数a, bの最小公倍数(LCM)を求めるには、aとbをまず掛け合わせて、その値をaとbの最大公約数(GCD)で割れば良いということです。
16と24の最小公倍数(LCM)の例では以下のようになります。

LCM(16, 24) = (16 * 24) / GCD(16, 24) = 384 / 8 = 48

Kotlinで最小公倍数(LCM)を求めるプログラム

以上を踏まえて、Kotlinで最小公倍数(LCM)を求めるプログラムを書いてみると以下のようになります。

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("lcm(%d, %d) = %d%n", a, b, lcm(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)
fun lcm(a: Int, b: Int): Int = (a * b) / gcd(a, b)

main関数では、まずScannerを使って標準入力を受け付けるようにします。
そして、nextInt()で2つの数字a, bを取得します。
最後に、lcm(a, b)の計算結果を出力しています。

gcd(a, b)は、aとbの最大公約数(GCD)を求める関数です。
ユークリッドの互除法を使って計算しています。

lcm(a, b)は、aとbの最小公倍数(LCM)を求める関数です。
aとbを掛け合わせた値から、aとbの最大公約数(GCD)を割ることで最小公倍数(LCM)を求めています。

プログラム自体はかなりシンプルですよね。

プログラムの実行結果

上記プログラムの実行結果の例は以下のようになります。
ここでは、16と24の最小公倍数(LCM)を求めてみました。
すると、確かにその値は48となっていて、正しく求められているのが分かりますね。

16 24
lcm(16, 24) = 48

ひとこと

今回は、Kotlinで最小公倍数(LCM)を求めるプログラムを作成してみました。
最大公約数(GCD)を求めることができれば、最小公倍数(LCM)は簡単に計算することができることが分かりますね。

最大公約数(GCD)と最小公倍数(LCM)は、いわばセットのようなものです。
プログラミングの練習問題としてもちょうど良いと思いますので…。
あなたも得意なプログラミング言語で、これらを求めるプログラムを作成してみてはいかがでしょうか?