[Kotlin] ユークリッドの互助法を用いて最小公約数・最小公倍数の計算を実装する
目次
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。(「ユークリッドの互除法 - Wikipedia」より引用)
上記のユークリッドの互助法をKotlinのコードに当てはめると、最小公約数(Greatest Common Divisor)を求める処理は以下のように再帰を用いて実装できます。末尾再帰最適化を適用できますので、 tailrec
キーワードを付けています。
// 最小公約数
tailrec fun gcd(a: Long, b: Long): Long =
if (b == 0L) a
else gcd(b, a % b)
最小公倍数(Least Common Multiple)を求める処理については、2つの数の積を最小公約数で除算すればよいです。上記の gcd
関数を用いて以下のように実装できます。 (a * b) / gcd(a, b)
としていないのは、 ()
を減らすための細かいテクニックです(コードゴルフ)。
// 最小公倍数
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
ここまで頑張って実装してきたのですが、JavaのBigIntegerに gcd
が存在しますので、こちらを使うと実務上は楽ができるかもしれません。以下のコードは、AtCoder Beginner Contest 148のC問題に対する、BigIntegerを用いた自分の解答です。
import java.math.*
fun main() {
val (a, b) = readLine()!!.split(' ').map(::BigInteger)
println(a / a.gcd(b) * b)
}
Reference
- ユークリッドの互除法 - Wikipedia(最終アクセス日:2022年3月18日)
- C - Snack(最終アクセス日:2022年3月18日)
- 提出 #29608584 - AtCoder Beginner Contest 148
書いている人 😎

茨城県つくば市在住のモバイルアプリケーションアーキテクト(Androidが得意です)。モバイルアプリのアーキテクチャ、自動テスト、CI/CDに興味があります。いわゆる「レガシーコード」のリファクタリング・リアーキテクチャが好きです。
👉 もっと詳しく
著書 ✍
Android 依存性注入 ヒッチハイク・ガイド🧳
Androidアプリでの依存性注入(Dependency Injection)に入門するためのガイダンスです。依存性注入の概念やメリットを理解し、Dagger Hiltを用いてAndroidアプリに適用する方法を解説しています。
ソフトウェアデザイン 2023年6月号📚
特集「クリーンアーキテクチャとは何か?」の第5章「モバイルアプリ開発における実践」を執筆しました。
Android クリーンアーキテクチャ ヒッチハイク・ガイド🧳
Androidアプリでのクリーンアーキテクチャに入門するためのガイダンスです。クリーンアーキテクチャの概念を理解し、Androidアプリに適用する方法を解説しています。
Android ユニットテスト ヒッチハイク・ガイド🧳
Androidアプリのユニットテストに入門するためのガイダンスです。初学者が混乱せずにAndroidアプリのユニットテストを書き始めることができる、ということを目的としています。
Android MVVMアーキテクチャ入門🛠
Androidアプリ開発の初学者に向けた、MVVM(Model-View-ViewModel)アーキテクチャの入門書を書きました。初学者の方を確実にネクストレベルに引き上げる技術書です。NextPublishingより出版されています。
関連記事 👀
- [Kotlin] 関数定義が1つだけのinterfaceは `fun interface` で定義できる
- ランチタイムLT会 #1で「何故、UseCaseは1メソッドなのか」というLTをしました
- DroidKaigi.collect{ #1@Tokyo }で「例外を投げるな、値を返せ」というLTをしました
- [Kotlin] 末尾カンマ
- [Kotlin] ifを愛でる