2値の最大公約数と最小公倍数 ~ユークリッドの互除法~

プログラムの問題で2つの値の最大公約数と最小公倍数を求めるものが出てきた。

まず考えついたのは力技による解決だったけれども
書いたところでためにならないので他のやり方を探した。

ユークリッドの互除法 - Wikipedia

これは最大公約数を求めるもので
最小公倍数は2値をかけたものを最大公約数で割ると求められる。

Javaで書いた。

private static long gcd(long a, long b) {
    long r = -1;
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

こちらは再帰で書いたもの

private static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

色々調べて行く過程で素因数分解で求める方法とかも出てきた。
この手のは自分の仕事でPHP書く分には出てこないことだけど、解くのは面白い。