最小公倍数・最大公約数

小ネタ

小ネタです。プログラミングをしていると、最小公倍数とか最大公約数を求めよ。
みたいなシーンに遭遇します。以下のプログラムで簡単に求められます。

public class Sample {

    public static void main(String[] args) {

        long a = 10001;
        long b = 959;
        System.out.println("gcd: " + MathUtils.gcd(a, b));
        System.out.println("lcm: " + MathUtils.lcm(a, b));

    }

    static class MathUtils {
        /**
        * 最大公約数
        * */
        public static long gcd(long a, long b) {
            return (b == 0) ? a : gcd(b, a % b);
        }
        /**
        * 最小公倍数
        * */
        public static long lcm(long a, long b) {
            return a * b / gcd(a, b);
        }
    }
}

理論的には、最大公約数(gcd)を求める際にユークリッドの互除法を使用しており、最小公倍数(lcm)を求める際には を利用しています。