Javaで2つの数の公約数の個数を求めるプログラムの書き方

この記事では、Javaを使って2つの整数の公約数(共通の約数)の個数を求めるプログラムを紹介します。再帰処理によるユークリッドの互除法で最大公約数(GCD)を計算し、その約数を効率よく数える手法を、サンプルコードとともにわかりやすく解説します。

サンプルコード

public class Demo{
    static int find_gcd(int val_1, int val_2){
        if (val_1 == 0)
        return val_2;
        return find_gcd(val_2%val_1,val_1);
    }
    static int common_divisors(int val_1,int val_2){
        int no = find_gcd(val_1, val_2);
        int result = 0;
        for (int i=1; i<=Math.sqrt(no); i++){
            if (no%i==0){
                if (no/i == i)
                    result += 1;
                else
                    result += 2;
            }
        }
        return result;
    }
    public static void main(String args[]){
        int val_1 = 68, val_2 = 34;
        System.out.println("The common divisors between the two numbers is ");
        System.out.println(common_divisors(val_1, val_2));
    }
}

実行結果

The common divisors between the two numbers is
4

プログラムの仕組み

1. 最大公約数を求める(find_gcdメソッド)

Demoクラスには、2つの引数を受け取って最大公約数を返す静的メソッド find_gcd が定義されています。このメソッドはユークリッドの互除法を再帰的に適用しており、第1引数が0になった時点で、残った第2引数が最大公約数として返されます。

2. 公約数の個数を数える(common_divisorsメソッド)

common_divisors メソッドでは、まず find_gcd を呼び出して2つの数の最大公約数を取得します。その後、1から最大公約数の平方根まで順にループしながら、以下の条件で約数を数えます。

• 最大公約数を現在の値 i で割り切れる場合、i は約数です。
• 「最大公約数 ÷ i」と「i」が同じ値になる場合(平方数の平方根など)は、重複を避けるためカウントを1だけ増やします。
• それ以外の場合は、約数は「i」と「最大公約数 ÷ i」のペアで存在するため、カウントを2増やします。

この方法により、1から最大公約数まで全てを調べる代わりに、平方根までのループだけで済むため、計算量をO(√n)に抑えられ、大きな数でも高速に処理できます。

3. mainメソッドでの実行

mainメソッドでは、例として val_1 = 68、val_2 = 34 の2つの値を初期化し、common_divisors メソッドを呼び出しています。68と34の最大公約数は34であり、その約数は「1、2、17、34」の4つなので、実行結果として「4」が出力されます。