Kotlinで最大公約数（GCD）と最小公倍数（LCM）を求める方法をやさしく解説！数学アルゴリズム入門

Kotlinで最大公約数（GCD）と最小公倍数（LCM）を求める方法

先生と生徒の会話形式で理解しよう

生徒

「Kotlinで最大公約数とか最小公倍数って計算できるんですか？」

先生

「もちろんできます。Kotlinでは数値計算や数学アルゴリズムも簡単に実装できます。最大公約数は英語でGCD、最小公倍数はLCMと呼ばれます。」

生徒

「数学の授業で聞いたことがあります。でもプログラムでどう書くのか想像できません。」

先生

「大丈夫です。Kotlinの基本文法を使えば初心者でも理解できます。今回は最大公約数の求め方と、それを使った最小公倍数の計算方法を丁寧に解説していきます。」

生徒

「Kotlinの数学アルゴリズムの勉強にもなりそうですね。」

先生

「その通りです。それではKotlinでGCDとLCMを求める方法を順番に見ていきましょう。」

1. 最大公約数（GCD）とは何か

最大公約数とは、二つ以上の数値を割り切ることができる数の中で、最も大きい数のことを指します。英語ではGreatest Common Divisorと呼ばれ、略してGCDと書きます。

例えば、12と18という数字を考えてみましょう。この2つの数を割り切ることができる数字を調べると、次のようになります。

12の約数 1 2 3 4 6 12
18の約数 1 2 3 6 9 18

この中で両方に共通している数字は、1 2 3 6です。その中で一番大きい数字は6なので、12と18の最大公約数は6になります。

プログラミングでは、数学の計算、暗号処理、アルゴリズムの最適化、数値計算などでGCDが使われることがあります。Kotlinでもこのような数学アルゴリズムを簡単に実装できます。

2. Kotlinで最大公約数を求める基本的な考え方

Kotlinで最大公約数を求める方法はいくつかありますが、最も有名なのがユークリッドの互除法というアルゴリズムです。

ユークリッドの互除法とは、次のようなルールで計算する方法です。

大きい数を小さい数で割る
余りを求める
割る数と余りで同じ計算を繰り返す
余りが0になったときの割る数が最大公約数

少し難しく見えるかもしれませんが、実際はとてもシンプルな処理です。例えば48と18の最大公約数を計算してみましょう。

48 ÷ 18 = 余り12
18 ÷ 12 = 余り6
12 ÷ 6 = 余り0

余りが0になったときの割る数は6なので、最大公約数は6になります。

3. Kotlinで最大公約数（GCD）を計算するプログラム

それでは実際にKotlinで最大公約数を求めるプログラムを書いてみましょう。ユークリッドの互除法をwhile文で実装します。


fun gcd(a: Int, b: Int): Int {
    var x = a
    var y = b

    while (y != 0) {
        val temp = y
        y = x % y
        x = temp
    }

    return x
}

fun main() {
    val result = gcd(48, 18)
    println("最大公約数は: $result")
}

このプログラムでは、%という記号を使っています。これは余りを求める演算子です。プログラミングではモジュロ演算子と呼ばれます。

whileは繰り返し処理の命令です。条件が成立している間、同じ処理を何度も実行します。このプログラムでは余りが0になるまで計算を繰り返しています。

このようにKotlinでは数学アルゴリズムをシンプルなコードで実装できます。


最大公約数は: 6

4. 再帰関数を使ってGCDを計算する方法

Kotlinでは再帰関数という書き方でも最大公約数を求めることができます。

再帰関数とは、関数の中で自分自身を呼び出すプログラムの書き方です。数学アルゴリズムやデータ処理でよく使われます。

ユークリッドの互除法は再帰と相性が良いアルゴリズムなので、次のように書くことができます。


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

fun main() {
    println(gcd(24, 36))
}

このプログラムでは、bが0になったときに計算を終了します。それ以外の場合は、次の計算を再びgcd関数に渡します。

このような再帰アルゴリズムは、Kotlinの数学処理やアルゴリズム学習で非常によく登場します。

5. 最小公倍数（LCM）とは何か

次に最小公倍数を理解しましょう。最小公倍数は英語でLeast Common Multipleと呼ばれ、略してLCMと書きます。

最小公倍数とは、複数の数の共通の倍数の中で一番小さい数のことです。

例えば6と8を考えてみます。

6の倍数 6 12 18 24 30
8の倍数 8 16 24 32

この中で共通している最初の数字は24です。つまり6と8の最小公倍数は24になります。

プログラミングでは、周期計算、スケジュール処理、時間管理アルゴリズムなどでLCMが使われることがあります。

6. Kotlinで最小公倍数（LCM）を計算する方法

実は最小公倍数は最大公約数を使って簡単に計算できます。次の公式を使います。

二つの数の掛け算を最大公約数で割ると最小公倍数になります。

つまり次の計算式になります。

LCM = a × b ÷ GCD

この公式をKotlinのプログラムで書くと次のようになります。


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

fun lcm(a: Int, b: Int): Int {
    return (a * b) / gcd(a, b)
}

fun main() {
    val result = lcm(6, 8)
    println("最小公倍数は: $result")
}

このように最大公約数の関数を作っておくと、最小公倍数の計算も簡単に作ることができます。Kotlinの関数を組み合わせることで、数学アルゴリズムの再利用ができるようになります。


最小公倍数は: 24

7. Kotlinで複数の数の最大公約数を求める

実際のプログラムでは二つの数だけでなく、複数の数の最大公約数を求めたいこともあります。

その場合は、二つずつ計算していけば求めることができます。


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

fun main() {

    val numbers = listOf(24, 36, 60)

    var result = numbers[0]

    for (i in 1 until numbers.size) {
        result = gcd(result, numbers[i])
    }

    println("最大公約数は: $result")
}

このプログラムではlistOfというKotlinの機能を使っています。これは複数の値をまとめて保存できるデータ構造です。

for文を使って順番に最大公約数を計算していくことで、複数の数値のGCDを求めることができます。Kotlinの数値計算や数学アルゴリズムの基礎として、とても重要なテクニックです。


最大公約数は: 12

Kotlinを基礎からしっかり学びたい人や、 Java経験を活かしてモダンな言語にステップアップしたい人には、定番の入門書がこちらです。

基礎からわかるKotlinをAmazonで見る

※ Amazon広告リンク

まとめ

Kotlinで学ぶ最大公約数と最小公倍数の重要ポイント

ここまで、Kotlinを使った最大公約数と最小公倍数の求め方について詳しく学んできました。最大公約数は複数の整数を割り切ることができる数の中で最も大きい数であり、最小公倍数は複数の整数の共通の倍数の中で最も小さい数を意味します。これらの数学的な考え方は学校の算数や数学でも登場しますが、プログラミングの世界でも非常に重要な基礎知識です。

Kotlinのようなモダンなプログラミング言語では、数値計算や数学アルゴリズムをシンプルなコードで実装できます。特にユークリッドの互除法は、最大公約数を効率よく求める代表的なアルゴリズムであり、多くのプログラミング言語でも利用されています。Kotlinでもwhile文や再帰関数を使うことで、このアルゴリズムを簡単に表現できます。

プログラミング学習では、数学アルゴリズムを実際のコードで書いてみることが理解を深める近道になります。Kotlinの関数、条件分岐、繰り返し処理、再帰関数といった基本文法を組み合わせることで、最大公約数の計算ロジックを自然な形で表現できるようになります。

ユークリッドの互除法の基本を振り返る

最大公約数を求めるときに使用したユークリッドの互除法は、非常に古くから知られている数学アルゴリズムです。この方法では、二つの数の余りを使いながら計算を繰り返していき、最終的に余りがゼロになったときの数が最大公約数になります。

Kotlinではモジュロ演算子を使って余りを求めることができるため、互除法のロジックを短いコードで表現できます。while文を使う方法は処理の流れが分かりやすく、初心者にとって理解しやすい書き方です。


fun gcd(a: Int, b: Int): Int {
    var x = a
    var y = b

    while (y != 0) {
        val temp = y
        y = x % y
        x = temp
    }

    return x
}

このような関数を一度作っておくことで、さまざまなプログラムで最大公約数の計算を再利用できるようになります。Kotlinの関数設計はシンプルで読みやすいため、数学処理のコードでも可読性を保ちながら実装できます。

最大公約数を利用した最小公倍数の計算

最小公倍数の計算では、最大公約数を利用することで効率的な処理が可能になります。二つの数の積を最大公約数で割ることで最小公倍数を求めることができます。この関係式は数学でもよく知られている公式です。

Kotlinではこの公式をそのまま関数として実装できるため、最大公約数の関数を再利用するだけで最小公倍数の計算処理を作ることができます。関数の再利用はプログラミングの基本的な設計思想の一つであり、保守性の高いコードを書くために重要です。


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

fun lcm(a: Int, b: Int): Int {
    return (a * b) / gcd(a, b)
}

Kotlinの関数を組み合わせることで、数学アルゴリズムを整理された形で実装できます。このようなコード設計は、アルゴリズム学習だけでなく、実務のソフトウェア開発でも非常に役立ちます。

複数の数値に対応するアルゴリズム

実際のプログラムでは二つの数だけでなく、三つ以上の数値の最大公約数を求めたい場面もあります。そのような場合には、順番に最大公約数を計算していく方法がよく使われます。Kotlinではリスト構造と繰り返し処理を組み合わせることで簡単に実装できます。


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

fun gcdList(numbers: List<Int>): Int {

    var result = numbers[0]

    for (i in 1 until numbers.size) {
        result = gcd(result, numbers[i])
    }

    return result
}

このようにKotlinのリスト構造とループ処理を組み合わせることで、複数の整数に対する最大公約数計算も柔軟に対応できます。数値アルゴリズムを実装する際には、このようなデータ構造の使い方も重要なポイントになります。

Kotlinで最大公約数や最小公倍数を扱うことは、数学アルゴリズムの理解だけでなく、関数設計、再帰処理、数値計算の基礎を学ぶ良いトレーニングになります。アルゴリズム学習の入り口としても非常におすすめのテーマです。

先生と生徒の振り返り会話

生徒

「Kotlinで最大公約数や最小公倍数を計算する方法がこんなにシンプルだとは思いませんでした。ユークリッドの互除法もプログラムで見ると分かりやすいですね。」

先生

「その通りです。数学アルゴリズムは難しく感じることがありますが、Kotlinのようなプログラミング言語で実装すると処理の流れがはっきり見えるようになります。」

生徒

「while文を使う方法と再帰関数を使う方法の両方があるのも面白かったです。再帰関数は最初少し不思議に感じました。」

先生

「再帰関数はアルゴリズムの世界でよく使われる重要な考え方です。最大公約数の計算だけでなく、探索アルゴリズムやデータ構造でも登場します。」

生徒

「最大公約数の関数を作ると最小公倍数も簡単に計算できるのが印象的でした。関数の再利用って大事なんですね。」

先生

「その理解はとても重要です。プログラム設計では同じ処理を何度も書くのではなく、関数としてまとめて再利用することが基本になります。」

生徒

「Kotlinで数学アルゴリズムを学ぶと、プログラミングと数学がつながっていることがよく分かりますね。」

先生

「まさにその通りです。最大公約数、最小公倍数、ユークリッドの互除法のような基礎的なアルゴリズムを理解しておくと、今後のプログラミング学習やアルゴリズム学習にも大きく役立ちます。ぜひ自分でも数値を変えて試してみてください。」

【未経験OK】Kotlinで始めるプログラミング入門｜ゼロから「動く喜び」を体験する60分

「プログラミングを始めたい」を形にする。最新言語Kotlinで楽しむ、ものづくりの第一歩。

本講座は、プログラミング経験が全くない方のためのエントリー講座です。「コードを書くってどういうこと？」という基本から、世界中で使われている最新言語Kotlin（コトリン）を使って、実際にプログラムを動かすまでを体験します。難しい理屈よりも、まずは「自分の手で動かす楽しさ」を最短距離で実感していただきます。