okuzawatsの日記

Android / Kotlin Enthusiast 🤖

ユークリッドの互助法を用いて最小公約数・最小公倍数の計算を実装する

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

  1. ユークリッドの互除法 - Wikipedia(最終アクセス日:2022年3月18日)
  2. C - Snack(最終アクセス日:2022年3月18日)
  3. 提出 #29608584 - AtCoder Beginner Contest 148

#Kotlin

About me 😎

profile

茨城県つくば市在住のソフトウェアエンジニアです。専門領域はAndroidアプリ開発で、特にアーキテクチャに興味があります。某社でAndroidアプリ開発のテックリードをしています。

Jetpack ComposeによるAndroid MVVMアーキテクチャ入門の著者です。

👉 もっと詳しく

Writing 📝

Android MVVMアーキテクチャ入門

Androidアプリ開発の初学者に向けた、MVVM(Model-View-ViewModel)アーキテクチャの入門書を書きました。初学者の方を確実にネクストレベルに引き上げる技術書です。

👉 もっと詳しく

See Also 👀