ユークリッドの互除法 最大公約数 number-theory

ユークリッドの互除法による最大公約数

ユークリッドの互除法による最大公約数
Feb. 2, 2020, 1:51 p.m.

目次

用途

2つの整数の最小公約数を求める.

アルゴリズム

ユークリッドの互除法と呼ばれるアルゴリズム.

2つの数のうち小さい方を$x$、大きい方を$y$とおく.

次に割る数$y$が0になるまで以下を繰り返す

  • r = x % y
  • x = y
  • y = r

xの最後の値が最大公約数.

計算量

%を$b$回繰り返すとすると、

$$
O(\log b)
$$

コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Int gcd(Int x, Int y) {
  if (x > y) swap(x, y);

  Int r;
  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}