ユークリッドアークほう

概要

2つの自然数の最大公約数を得るためには,2から2つの自然数のうちの小さな自然数を分けることができ,最大公約数を得ることができる.
一般的に用いられる共通の素数を探すことにより,最小公倍数,最大公倍数を探し出す方法でアルゴリズムを作成し,時間的複雑度はO(n)であるが,ユークリッドアーク負荷法により時間的複雑度をO(logn)に低減できる.
求め方は以下の通り

ユークリッドアーク除算の使用

ユークリッドアーク除去法で最大公約数を求める

ユークリッドアーク法を理解するためにはMOD演算を理解する必要がある.
MOD演算:二つの値の和を求める演算
まず大数を小数で割った余数を求める.(MOD操作)

1112 mod 695 = 417

そして、除算した数と余りでMOD演算を行う.

695 mod 417 = 278

この過程を繰り返します.

417 mod 278 = 139
278 mod 139 = 0

剰余が0の場合、最後の計算で除算された139は1112および695の最大公約数となる.
すなわち,ユークリッドアーク除算はMOD演算を繰り返す.

ユークリッドアークの使い方を理解する

どのようにユークリッド弧除法で最大公約数(GCD)を求めますか?
1112と695を棒の奇異として表すと、2つの数の最大公約数Nに分けられる.
最大公約数は129なので8格、5格に分かれていますが、実際には知りません.
しかし,1112と695は最大公約数Nの倍数であることが分かった.
上の図に示すように、MOD演算は1112および695が繰り返される.

この図から,演算中に残った417,278,139はいずれもNの倍数であり,同じ最大公因数を有することがわかる.
278は139に分けられ、残りは0であり、このとき最大公約数Nは139である.
関連問題:白駿GCD合
ソース:https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95