すずろぐ

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

スポンサーリンク

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

number

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

今日はちょっとしたJavaプログラムを作成してみました。 今回は、アルゴリズムの復習として、最大公約数(GCD)を求めるという事をしてみました。

最大公約数を求める方法としては、ユークリッドの互除法が有名ですよね。 このアルゴリズムをプログラムで実装して、動作を確認しました。

せっかくなので、そのプログラムを載せておこうと思います。 非常に簡単なプログラムなのですぐに理解ができるのではないでしょうか?

最大公約数(GCD)とは?

最大公約数というのは、2つ以上の正の整数に共通な約数(公約数)のうち最大のものをいいます。 例えば、64と24の最大公約数を普通に求めてみると…。

64の約数: 1,2,4,8,16,32,64
24の約数: 1,2,3,4,6,8,12,24

このことから、2つの数字の約数の中で共通する最大の約数は8ですね。 つまり、64と24の最大公約数は8となります。

ユークリッドの互除法とは?

ユークリッドの互除法というのは、この最大公約数を求める際に用いる解法アルゴリズムです。 2つの自然数a,bの最大公約数をGCD(a, b)とします。 a>b>0とした場合、aをbで割った余りをrとすると、GCD(a, b) = GCD(b, r)が成り立ちます。 r = 0となった時のbの値が求める最大公約数となります。

さきほどの64と24の最大公約数をこのユークリッドの互除法で求めてみると…。

GCD(64, 24) 
= GCD(24, 16)
= GCD(16, 8)
= GCD(8, 0)
= 8

このように簡単に最大公約数を求めることができます。

最大公約数を求めるメソッドgcd(m, n)

ここでは、Javaでの実装例を載せます。 実装の仕方には、いくつかパターンがあると思いますが、今回は再起呼び出しを使って実装してみました。

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);
}

まず最初のif文で、mの方がnよりも大きくなるようにしておきます。 そして、小さいほうの数字nが0の場合には、mの値を返します。 そうでなければ、再帰的にgcdを呼び出します。 やっていることは非常に簡単ですよね。

サンプルプログラム

上記のgcd()を使って、実際に最大公約数を求めるサンプルプログラムを作成してみました。 ユーザーに2つの数字を入力してもらって、それらの最大公約数を求めてコンソールに表示するというものです。 このサンプルプログラム自体も非常にシンプルですので、ちょっとプログラミングしている方ならすぐに理解できると思います。

import java.util.Scanner;

public class GCD {
    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("gcd(%d, %d) = %d%n", m, n, gcd(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);
    }
}

実行結果

サンプルプログラムの実行結果の例を載せておきます。 ここでは、64と24の最大公約数を求めてみました。 正しく8という値が表示されているのが分かりますね。

数字を2つ入力してください。
64
24
gcd(64, 24) = 8

ひとこと

アルゴリズムというのは、予め知っていて使いこなせると非常に便利なのですよね。 ユークリッドの互除法はまだ簡単な方ですが、他にもアルゴリズムというのは存在します。 もっと色々なアルゴリズムについて勉強してみたいですね。

関連

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