ユークリッド互除法とは？
ゆーくりっどごじょほう
ユークリッド互除法とは、二つの整数の最大公約数を効率的に求めるためのアルゴリズムです。
ユークリッド互除法（Euclidean algorithm）は、二つの正の整数の最大公約数（GCD）を求める最古かつ最も広く知られたアルゴリズムのひとつです。古代ギリシャの数学者ユークリッドが著書『原論』（紀元前3世紀頃）に記したことからこの名称がつけられました。
基本的な仕組みは「二つの整数 a と b（a > b）があるとき、a と b の最大公約数は a を b で割った余り r と b の最大公約数に等しい」という性質を繰り返し利用することです。具体的な手順は以下のとおりです。
- a を b で割り余り r を求める（a = b×q + r）
- 余り r が 0 なら、b がその時点での最大公約数
- r が 0 でなければ、a に b を、b に r を代入して手順1を繰り返す
例として 252 と 105 の最大公約数を求める場合、252 ÷ 105 = 2 余り 42 → 105 ÷ 42 = 2 余り 21 → 42 ÷ 21 = 2 余り 0 となり、最大公約数は 21 です。
ユークリッド互除法の計算量は入力の桁数に対して対数的（O(log min(a,b))）であり非常に効率的です。現代でもプログラミングでの分数の約分・座標計算・暗号理論（RSA暗号の鍵生成など）まで幅広い場面で応用されています。
使い方・例文
「プログラムで二つの数の最大公約数を求める際にユークリッド互除法を使うと、数が大きくても素早く計算できる」という場面でよく登場します。
この用語をシェア
最終更新: