Javaで最大公約数、最小公倍数を求める。

Javaで最大公約数、最小公倍数を求めるメソッドを作成した。引数で受け取った2つの引数の最大公約数、最小公倍数をそれぞれ求めて返す。

    // 最大公約数を求める。
    int calcGcd(int m, int n) {
        if (m <= 0 || n <= 0) {
            throw new IllegalArgumentException("Arguments must be 1 and over.");
        }
        if(m < n) {
            int tmp = m;
            m = n;
            n = tmp;
        }
        int remainder = 0;
        while ((remainder = m % n) != 0) {
            m = n;
            n = remainder;
        }
        return n;
    }

    // 最小公倍数を求める。
    int calcLcm(int m, int n) {
        return m * n / calcGcd(m, n);
    }

calcLcmにて、最小公倍数は「m × n / 最大公約数」で求めている。
これは、例えば、m と n の最大公約数が a であり、
・m = a × b × c
・n = a × d × e
で表現できたとすると、
m と n の最小公倍数 x は、m と n の要素を含み、かつ、最小なもの (他に余分な要素を含まないもの) なので、
x = a × (b × c) × (d × e) = (a × b × c) × (a × d × e) / a = m × n / 最大公約数
となる。
これにより、最小公倍数は「m × n / 最大公約数」で求められることが分かる。