ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)

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


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


 概要は「正の整数 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 : 数値1(>0)
* @param b : 数値2(>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 となるが、このとき「互いに素」であることがわかる(お互いの共通の因子を持たない)。実はしばしばこの性質を利用する解法も見かけるので、覚えておいた方が良いだろう。

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

●最大公約数を求める [ユークリッドの互除法](再帰版)
/**<h1>最大公約数を求める(Greatest Common Divisor)[ユークリッドの互除法](再帰版)</h1>
* @param a : 数値1(>0)
* @param b : 数値2(>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 [解答例は載ってない]
平面の2つの格子点 P1 = (x1, y1), P2 = (x2, y2) が与えられます。
線分 P1, P2 上には P1, P2 以外にいくつの格子点が存在しますか?
(格子点とは) 座標平面(or 座標空間)において,各成分が全て整数であるような点。

制約
・-109 <= x1, x2, y1, y2 <= 109

入力例
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() は0で除算できない(P1, P2 が同じ点、または x 軸, y 軸のどちらかが同じ)ことだけ注意しよう。

- - - - - - - - - - - - - - - - - - 
●最小公倍数を求める

 ついでにもう1つ、最小公倍数(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 : 数値1(>0)
* @param b : 数値2(>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版)
元の分数を入力:
/



約分された分数:
/

最大公約数(gcd):
最小公倍数(lcm):


(関連記事)
【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
【Java】拡張ユークリッドの互除法
【Java】約数を求める
【Java】素因数分解をする
【Java】素数判定①(試し割り法)


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  約数  練習問題  アルゴリズム 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/215-ea06f4e6
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop