【Java】最大公約数・最小公倍数

最大公約数

整数aと整数bの最大公約数は、お互いの素因数について指数の最小値を取ることで求めることができます。

$$105 = 2^0 × 3^1 × 5^1 × 7^1$$

$$180 = 2^2 × 3^2 × 5^1 × 7^0$$

$$最大公約数：2^0 × 3^1 × 5^1 × 7^0 = 15$$

コード例

import java.util.*;

public class Main {
    // 素因数分解
    // 整数 a 及び b を受け取り、素因数分解をおこなって (素因数=個数) の連想配列を返す
    static HashMap<Integer, Integer> factorize(int n) {
        HashMap<Integer, Integer> primes = new HashMap<>();

        for (int i = 2; i * i <= n; i++) {
            if (n % i > 0) {
                continue;
            }
            int exp = 0;
            while (n % i == 0) {
                exp++;
                n /= i;
            }
            primes.put(i, exp);
        }

        if (n != 1) {
            primes.put(n, 1);
        }
        
        return primes;
    }

    // 連想配列 primes を受け取り、最大公約数を返す
    static int calcGcd(int a, int b) {
        HashMap<Integer, Integer> tableA = factorize(a);
        HashMap<Integer, Integer> tableB = factorize(b);
        HashMap<Integer, Integer> tableGcd = new HashMap<>();
        
        for (int prime : tableA.keySet()) {
            int exp = tableA.get(prime);
            if (tableB.containsKey(prime)) {
                exp = Math.min(exp, tableB.get(prime));
                tableGcd.put(prime, exp);
            }
        }
        int gcd = 1;
        for (int factor : tableGcd.keySet()) {
            int exp = tableGcd.get(factor);
            for (int i = 0; i < exp; i++) {
                gcd *= factor;
            }
        }
        return gcd;
    }

    public static void main(String[] args) {
        int a = 105;
        int b = 180;
        int gcd = calcGcd(a, b);
        System.out.println(a + " と " + b + " の最大公約数は " + gcd);
    }
}

コード例の解説

factorizeメソッドは、素因数分解の時と全く同じなので、解説を割愛します。
calcGcdメソッドについてのみ解説します。
まずは、整数aを渡した時の連想配列tableAと、整数bを渡した時の連想配列tableB下記の通りです。

tableA = {3=1, 5=1, 7=1}
tableB = {2=2, 3=2, 5=1}

Keyは=の左側であり、Valueは=の右側です。

1. 連想配列tableGcdを初期化します。
2. 拡張for文により、連想配列tableAの1つ目のKey=3を、変数primeに代入します。
3. 連想配列tableAのKey=3に対応するValue=1を変数expに代入します。
4. if文の条件式の連想配列tableBに変数prime=3というKeyが含まれているか、を満たすので、
5. tableAのKey=3に対応するValue=1が代入された変数expと、tableBのKey=3に対応するValue=2を比較して小さい方の1を、変数expに代入して更新します。
6. 連想配列tableGcdに、3=1を代入します。
7. 拡張for文により、連想配列tableAの2つ目のKey=5を、変数primeに代入します。
8. 連想配列tableAのKey=5に対応するValue=1を変数expに代入します。
9. if文の条件式の連想配列tableBに変数prime=5というKeyが含まれているか、を満たすので、
10. tableAのKey=5に対応するValue=1が代入された変数expと、tableBのKey=5に対応するValue=1を比較して小さい方の1を、変数expに代入して更新します。
11. 連想配列tableGcdに、5=1を代入します。
12. 拡張for文により、連想配列tableAの最後のKey=7を、変数primeに代入します。
13. 連想配列tableAのKey=7に対応するValue=1を変数expに代入します。
14. if文の条件式の連想配列tableBに変数prime=7というKeyが含まれているか、を満たさないので、if文を抜けます。そして、拡張for文も抜けます。
    この時の連想配列tableGcdは、下記の通りです。

    {3=1, 5=1}
    

15. 変数gcdを1で初期化します。
16. 拡張for文により、連想配列tableGcdの1つ目のKey=3を、変数factorに代入します。
17. 連想配列tableGcdのKey=3に対応するValue=1を変数expに代入します。
18. for文で１回だけループして、
19. 変数gcdを3に更新します。
20. 拡張for文により、連想配列tableGcdの最後のKey=5を、変数factorに代入します。
21. 連想配列tableGcdのKey=5に対応するValue=1を変数expに代入します。
22. for文で１回だけループして、
23. 変数gcdを15に更新し、拡張for文を抜けます。
24. 戻り値として変数gcdを返します。

---

最小公倍数

整数aと整数bの最小公倍数は、お互いの素因数について指数の最大値を取ることで求めることができます。

$$36 = 2^2 × 3^2$$

$$60 = 2^2 × 3^1 × 5^1$$

$$最小公倍数：2^2 × 3^2 × 5^1 = 180$$

コード例

import java.util.*;

public class Main {
    // 素因数分解
    // 整数 a 及び b を受け取り、素因数分解をおこなって (素因数=個数) の連想配列を返す
    static HashMap<Integer, Integer> factorize(int n) {
        HashMap<Integer, Integer> primes = new HashMap<>();

        for (int i = 2; i * i <= n; i++) {
            if (n % i > 0) {
                continue;
            }
            int exp = 0;
            while (n % i == 0) {
                exp++;
                n /= i;
            }
            primes.put(i, exp);
        }

        if (n != 1) {
            primes.put(n, 1);
        }

        return primes;
    }

    // 連想配列 primes を受け取り、最小公倍数を返す
    static int calcGcd(int a, int b) {
        HashMap<Integer, Integer> tableA = factorize(a);
        HashMap<Integer, Integer> tableB = factorize(b);
        HashMap<Integer, Integer> tableLcm = tableA;
        
        for (int prime : tableB.keySet()) {
            int exp = tableB.get(prime);
            if (tableA.containsKey(prime)) {
                exp = Math.max(exp, tableA.get(prime));
                tableLcm.put(prime, exp);
            }
            tableLcm.put(prime, exp);
        }
        
        int lcm = 1;
        for (int factor : tableLcm.keySet()) {
            int exp = tableLcm.get(factor);
            for (int i = 0; i < exp; i++) {
                lcm *= factor;
            }
        }
        return lcm;
    }

    public static void main(String[] args) {
        int a = 36;
        int b = 60;
        int gcd = calcGcd(a, b);
        System.out.println(a + " と " + b + " の最大公約数は " + gcd);
    }
}

コード例の解説

下記の部分だけ解説します。

static int calcGcd(int a, int b) {
    HashMap<Integer, Integer> tableA = factorize(a);
    HashMap<Integer, Integer> tableB = factorize(b);
    HashMap<Integer, Integer> tableLcm = tableA;
    
    for (int prime : tableB.keySet()) {
        int exp = tableB.get(prime);
        if (tableA.containsKey(prime)) {
            exp = Math.max(exp, tableA.get(prime));
            tableLcm.put(prime, exp);
        }
        tableLcm.put(prime, exp);
    }
}

まずは、連想配列tableAと連想配列tableB及び連想配列tableLcm下記の通りです。

tableA = {2=2, 3=2}
tableB = {2=2, 3=1, 5=1}
tableLcm = {2=2, 3=2}

Keyは=の左側であり、Valueは=の右側です。

1. 拡張for文により、連想配列tableBの1つ目のKey=2を、変数primeに代入します。
2. 連想配列tableBのKey=2に対応するValue=2を変数expに代入します。
3. if文の条件式の連想配列tableAに変数prime=2というKeyが含まれているか、を満たすので、
4. tableBのKey=2に対応するValue=2が代入された変数expと、tableAのKey=2に対応するValue=2を比較して大きい方の2を、変数expに代入して更新します。
5. 連想配列tableGcdに、2=2を代入します。

   連想配列であるMapは、Keyの重複を許しません。
   したがって、put()メソッドで新しいKeyとValueのペアを追加する際、もし同じKeyが既に存在している場合は、古いValueが新しいValueで置き換えられます。

6. 拡張for文により、連想配列tableBの2つ目のKey=3を、変数primeに代入します。
7. 連想配列tableBのKey=3に対応するValue=1を変数expに代入します。
8. if文の条件式の連想配列tableAに変数prime=3というKeyが含まれているか、を満たすので、
9. tableBのKey=3に対応するValue=1が代入された変数expと、tableAのKey=3に対応するValue=2を比較して大きい方の2を、変数expに代入して更新します。
10. 連想配列tableGcdに、3=2を代入します。
11. 拡張for文により、連想配列tableBの最後のKey=5を、変数primeに代入します。
12. 連想配列tableBのKey=5に対応するValue=1を変数expに代入します。
13. if文の条件式の連想配列tableAに変数prime=5というKeyが含まれているか、を満たさないので、if文を抜けます。そして、拡張for文も抜けます。
14. 連想配列tableGcdに、5=1を代入します。
    この時の連想配列tableGcdは、下記の通りです。

    tableLcm = {2=2, 3=2, 5=1}
    

---

最大公約数・最小公倍数の関係

整数 a
整数 b
a と b の最大公約数 g
a と b の最小公倍数 l

上記の条件の場合は、下記の関係が成り立ちます。

$$a × b = g × l$$