【Java】最大公約数・最小公倍数を求める（ユークリッドの互除法）

2016/06/10 Fri [edit]

　以前ちらりと書いたが、「エラトステネスの篩」と同じように、コンピュータが存在する以前からある「最大公約数」(Greatest Common Divisor) を求めるアルゴリズムに「ユークリッドの互除法」というものがある。最古のアルゴリズムとも言われているが、コンピュータ時代になっても健在で、簡単でしかも高速なアルゴリズムとしてもよく利用されている。

■ユークリッドの互除法（非再帰版）
■ユークリッドの互除法（再帰版）
■線分上の格子点の個数を求める [gcd() 使用例]
■最小公倍数を求める [lcm()]
■約分・最大公約数・最小公倍数計算機

　概要は「正の整数 a, b (a >= b) について「a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる」(Wikipedia) となっているが、Wikipedia の右端にあるアニメーションを見た方がわかりやすい気がする(笑)。

　書き方もループで書いたものと再帰で書いたものをよく見かけるが、比較のためにも両方書いてみよう。

●最大公約数を求める [ユークリッドの互除法]（非再帰版）

/**<h1>最大公約数を求める(Greatest Common Divisor)[ユークリッドの互除法]</h1>
 * @param a ： 数値１(>0)
 * @param b ： 数値２(>0)
 * @return<b>int</b> ： 最大公約数 (なし=1 [互いに素])
 */
public static final int gcd(int a, int b) {
    //a > b にする（スワップ）
    if (a < b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    //ユークリッドの互除法
    int r = -1;
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }

    return a;    //b には r=0 の値が入るため、a を返す
}


//メインでは...
int a = 1920;
int b = 1080;
int d = gcd(a, b);
System.out.println("d = " + d);      //最大公約数
System.out.println(a + "/" + b + " = " + (a / d) + "/" + (b / d));    //約分に利用

d = 120
1920/1080 = 16/9

　例では 1920 と 1080 の最大公約数 d は 120 であり、それぞれを最大公約数(120)で割ると、約分と同じ意味になることを表している。1920x1080 はアスペクト比で有名なので、16 : 9 (16/9) が正しいのは検算しなくてもわかるだろう。

　関数冒頭で、a, b の大小関係を調べてスワップしているが、ユークリッドの互除法は「a, b が正の値で a >= b とするとき」となっているので、既知ならば削除しても構わない。

　また、最大公約数がないときは 1 となるが、このとき「互いに素」であることがわかる（お互いの共通の因子を持たない）。実はしばしばこの性質を利用する解法も見かけるので、覚えておいた方が良いだろう。

　もう１つ、ユークリッドの互除法は再帰の例としても挙げられるが、確かに非常に簡潔に書けるので、あまり負荷のかからない処理なら、こちらでも構わないだろう。

●最大公約数を求める [ユークリッドの互除法]（再帰版）

/**<h1>最大公約数を求める(Greatest Common Divisor)[ユークリッドの互除法]（再帰版）</h1>
 * @param a ： 数値１(>0)
 * @param b ： 数値２(>0)
 * @return<b>int</b> ： 最大公約数 (なし=1 [互いに素])
 */
public static final int gcd(final int a, final int b) {
    return (b == 0) ? a : gcd(b, a % b);
}


//メインでは...
int a = 1920;
int b = 1080;
int d = (a >= b) ? gcd(a, b) : gcd(b, a);    //a >= b にする
System.out.println("d = " + d);      //最大公約数
System.out.println(a + "/" + b + " = " + (a / d) + "/" + (b / d));    //約分に利用

d = 120
1920/1080 = 16/9

　こちらは随分簡潔になっているが、非再帰版は a, b の大小関係はチェックしてないので、注意しよう。心配ならサンプルのようにメインコードで調べれば良い。

　また、ループ版と再帰版とで実行速度を比べてみると、やはりループ版の方がわずかに速いが、それほど差はないので、計算量の小さいものなら問題なく使えるだろう。

　上の例では gcd() を約分に利用しているが、他にも色々と応用できる。例えば「線分上の格子点の個数」を求めてみよう。

●線分上の格子点の個数　(参考) アリ本 P.107 [解答例は載ってない]

平面の２つの格子点 P1 = (x1, y1), P2 = (x2, y2) が与えられます。
線分 P1, P2 上には P1, P2 以外にいくつの格子点が存在しますか？
(格子点とは) 座標平面（or 座標空間）において，各成分が全て整数であるような点。

制約
・-10⁹ <= x1, x2, y1, y2 <= 10⁹

入力例
P1 = (1, 11), P2 = (5, 3)

● 線分上の格子点の個数を求める gcd() での解法

int x1 = 1, y1 = 11;    //P1
int x2 = 5, y2 = 3;     //P2

int a = Math.abs(x1 - x2);
int b = Math.abs(y1 - y2);
int g = 1;

if (x1 == x2 && y1 == y2) {
    //0
} else if (x1 == x2) {
    g = b;
} else if (y1 == y2) {
    g = a;
} else {
    g = gcd(a, b);
}
System.out.println(g - 1);    //答え

//以下は具体的な座標の出力
int x = x1, y = y1, dx = 0, dy = 0;
if (x1 <= x2) {
    dx = (x2 - x1) / g;
    dy = (y2 - y1) / g;
} else {
    x = x2; y = y2;
    dx = (x1 - x2) / g;
    dy = (y1 - y2) / g;
}
for (int i = 1; i < g; i++) {
    if (i > 1) {
        System.out.print(", ");
    }
    System.out.print("(" + (x + i * dx) + ", " + (y + i * dy) + ")");
}
System.out.println();

3
(2, 9), (3, 7), (4, 5)

　単純に (x1, y1)-(x2, y2) の線分上でかつ整数となる点を全て調べても良いが、線分が大きくなると計算量が間に合わなくなる。その点、gcd() なら非常に軽い。gcd() は０で除算できない(P1, P2 が同じ点、または x 軸, y 軸のどちらかが同じ)ことだけ注意しよう。

　
●最小公倍数を求める

　ついでにもう１つ、最小公倍数(Least Common Multiple)も求めてみよう。

　Wikipedia にも書いてあるように「正の整数a, bに対して、最大公約数gcd(a, b)と最小公倍数lcm(a, b)との間には、gcd(a, b)×lcm(a, b) = ab という関係がある」となっているので、「gcd()」ができていれば、非常に簡単に作れる。

●最小公倍数を求める

/**<h1>最小公倍数を求める(Least Common Multiple)</h1>
 * @param a ： 数値１(>0)
 * @param b ： 数値２(>0)
 * @return<b>int</b> ： 最小公倍数
 */
public static final int lcm(final int a, final int b) {
    return a * b / gcd(a, b);
}


//メインでは...
int h = 16;
int v = 9;
int m = lcm(h, v);
System.out.println("m = " + m);

m = 144

　こちらも「gcd()」のおかげで随分と簡潔だ。内容は式を変形しただけのものに過ぎないので、説明はいらないだろう。

　「ユークリッド互除法」には「ax + by = gcd(a, b) となる a, b の最大公約数を求める」という「拡張ユークリッド互除法」というものもある。解となる整数 x, y の組を見つけることができるものなので、数学的な問題には役に立つことがあるかも知れない。実装は gcd() とそれほど変わらないので。覚えておいても損はないだろう。

■約分・最大公約数・最小公倍数計算機

ユークリッドの互除法で約分・最大公約数(gcd)・最小公倍数(lcm)を求める(JavaScript版)