すずろぐ

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

スポンサーリンク

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

number

こんにちは、すずしんです。

前回のプログラミングに関する記事では、ユークリッドの互除法を使って最大公約数(GCM)を求めるJavaプログラムを作成しました。 これに関連して、今回は最小公倍数(LCM)を求めるプログラムを作成してみることにしました。

最小公倍数とは?

最小公倍数は、2つ以上の正の整数の共通な倍数(公倍数)のうち最小のものをいいます。 例えば、16と24の最小公倍数は普通に計算すると以下のように求められます。

8 ) 16 24
   -------
     2  3

8 * 2 * 3 = 48

最小公倍数は、最大公約数を使っても求めることができます。 2つの自然数をm, nとして、それらの最小公倍数をLCM(m, n)、最大公約数をGCD(m, n)としたとき、以下のようになります。

LCM(m, n) = m * n / GCD(m, n)

今回の実装では、後者の方法で最小公倍数を求めることにします。

最小公倍数を求めるメソッドlcm(m, n)

最小公倍数を求めるメソッドlcm(m, n)の実装例は以下のような感じになります。

private static long lcm(long m, long n) {
    return m * n / gcd(m, n);
}

lcmメソッド中で使われているgcdメソッドの実装例は以下の通りです。

private static long gcd(long m, long n) {
    if(m < n) return gcd(n, m);
    if(n == 0) return m;
    return gcd(n, m % n);
}

それほど難しいことは特に無いですね。

サンプルプログラム

上記のlcmメソッドを使って、実際に最小公倍数を求めるサンプルプログラムを作成してみました。 ユーザーに2つの数字を入力してもらい、それらの最小公倍数をコンソールに表示するというものです。

import java.util.Scanner;

public class LCM {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("数字を2つ入力してください。");
        long m = in.nextLong();
        long n = in.nextLong();
        System.out.printf("LCM(%d, %d) = %d%n", m, n, lcm(m, n));
    }
    
    private static long gcd(long m, long n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }
    
    private static long lcm(long m, long n) {
        return m * n / gcd(m, n);
    }
}

実行結果

サンプルプログラムの実行結果の例は以下の通りです。 16と24の最小公倍数を求めてみました。 正しく48と表示されているのが分かりますね。

数字を2つ入力してください。
16
24
LCM(16, 24) = 48

ひとこと

最小公倍数をプログラムで求める場合には、今回のように最大公約数を元にして求めるのが簡単です。 実装方法もシンプルなので、プログラミングの練習にはもってこいの題材なのではないでしょうか?

関連

Java ユークリッドの互除法で最大公約数(GCD)を求めるプログラムを作成してみた