Algorithms/Mathematics/Greatest Common Divisor

Greatest Common Divisor

最大公約数, gcd

Outline

最大公約数とは、ある二つの整数の約数の中で最大のもののことであり、
aとbの最大公約数を&mimetex(gcd(a,b));と表す.
最大公約数は、例えば分数の約分のときなどに使う.
最大公約数の求め方には
説明の必要もないほど有名な
ユークリッドの互助法(Euclidean Algorithm)というアルゴリズムがある.
ユークリッドの互助法の実装方法としては、下に示したプログラム以外にも
再帰関数を用いる方法があるが、
例によって再帰関数は関数のオーバヘッドがあるので、
普通は使わない.
ICPCでもgcdを求めるときは、ユークリッドにお世話になる.

また、ユークリッドの互助法の応用として、
拡張ユークリッドの互助法(Extended Euclidean Algorithm?)
というアルゴリズムがある.

Program

ユークリッドの互助法

long gcd(long a, long b) {
  long t;

  while(b) {
    t = a % b;
    a = b;
    b = t;
  }

  return a;
}