Skip to content

最大公約数・最小公倍数 (Euclidean Algorithm)

概要

ユークリッドの互除法 (Euclidean Algorithm) により 2つの自然数 x, y の最大公約数 gcd(x, y), 最小公倍数 lcm(x, y) を求める. x, y の最大公約数が求まれば最小公倍数は lcm(x, y) = x / gcd(x, y) * y で求めることができる.

  • 計算量:

実装例

C/C++ (再帰関数)

typedef long long ll;

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}

C/C++ (非再帰)

typedef long long ll;

ll gcd(ll x, ll y) {
  while (y != 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}

Python3 (再帰関数)

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)

def lcm(x, y):
    return x//gcd(x, y)*y

Python3 (非再帰)

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x//gcd(x, y)*y

解説

  • アルゴリズムの正当性の証明

ユークリッドの互除法は2つの自然数 x, y について, gcd(x, y) が gcd(y, x % y) に等しいことを利用し, 第二引数が 0 になるまで操作を繰り返すことで最大公約数を求めている.

gcd(x, y) が gcd(y, x % y) と等しいことを示してみる.

自然数 x, y について, x を y で割った商を q, 余りを r とすると

ここである自然数 d を y と r の両方を割り切ることができる, すなわち y と r の公約数であるとする.

このとき, d は qy + r = x も割り切ることができるため, x を割り切ることもできる. よって, d は x と y の公約数でもある.

ゆえに, ある自然数 d が y と r の公約数ならば d は x と y の公約数でもある.

次に, 逆を示す.

ある自然数 d が x と y の公約数であるとする. このとき も d で割り切れるので d は y と r を割り切る.

ゆえに, ある自然数 d が x と y の公約数ならば d は y と r の公約数でもある.

以上のことから, x と y の公約数の集合は y と x % y の公約数の集合と等しいことが示され gcd(x, y) = gcd(y, x % y) も一致することが分かる.

  • 図形的な捉え方

最大公約数は幅, 高さがa, b の長方形を埋め尽くすことができるような正方形のなかで最大のものの一辺の長さに等しい.

上の画像のように長方形から正方形を切り落としていき最後に残った小さな正方形の一辺が gcd(a, b) となる.

  • 標準ライブラリ

C++, Python3 ともに標準ライブラリに gcd を求める関数が存在する.

C++ では標準ヘッダである algorithm をインクルードすると, __gcd() という関数が使え, Python3 では version 3.6未満では math.gcd() がそれ以降では fractions.gcd() が使える.

標準ライブラリの gcd を使うと, バージョンによって import するモジュールがどれであるかを意識する必要が生じるため, 自前の実装を使うほうが良いかもしれない.

使用例

関連する問題

参考文献