ユークリッドの互除法 2007/09/16

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

wikipediaに載っていたアルゴリズムをコードにしてみました。

ユークリッドの互除法

static int gcd(int m, int n) {
if (m < n)
return gcd(n, m);
if (n == 0)
return m;
int r = m % n;
if (r == 0)
return n;
// mをnで割った余りを新たにmとし、更にmとnを取り替えて3に戻る
return gcd(n, r);
}