ユークリッドアルゴリズムとは？
ゆーくりっどあるごりずむ
ユークリッドアルゴリズムとは、二つの整数の最大公約数を効率よく求める、古代から知られる数学的手法です。
ユークリッドアルゴリズム（Euclidean algorithm）は、二つの正の整数 a, b（a > b）の最大公約数（GCD）を求めるための手続きです。古代ギリシャの数学者ユークリッドが著書『原論』（紀元前300年頃）の中で記述しており、現存する最古のアルゴリズムのひとつとして知られています。
仕組みは「a を b で割った余りを r とすると、GCD(a, b) = GCD(b, r)」という性質を繰り返し適用することです。余りが0になったとき、最後の割る数が最大公約数となります。たとえば GCD(48, 18) は、48 = 18×2+12 → 18 = 12×1+6 → 12 = 6×2+0 となり、答えは6です。
ユークリッドアルゴリズムの特徴を整理すると以下のとおりです。
- 計算量は入力のビット数に対して多項式時間（非常に高速）
- 巨大な数でも実用的な速度で最大公約数を求められる
- 拡張ユークリッドアルゴリズムに発展させると整数係数の方程式の解も求まる
- RSA暗号など現代暗号理論の基礎としても活用されている
数学的に単純な原理でありながら効率性が高く、プログラミングでも最初に学ぶ古典的アルゴリズムとして位置づけられています。
使い方・例文
分数を約分するプログラムや、音楽のリズム周期の最小公倍数を求めるツールなど、ユークリッドアルゴリズムは日常的な計算処理の内部で幅広く使われています。
この用語をシェア
最終更新: