【独習】ユークリッド互除法とは

2020/5/2 2020/5/2 書き溜め

ユークリッド互除法を理解しているだろうか。
聞いたことがある程度の人もいれば、それがアルゴリズムであることまでは分かる人も多いだろう。
今回は、ユークリッド互除法を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

ユークリッド互除法

ユークリッド互除法とは、
2つの自然数の最大公約数を求める手法の一つである。

ユークリッド互除法では、
自然数のある性質を利用して計算を行う。

その性質とは下記である。

2つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると
a と b との最大公約数は b と r との最大公約数に等しい。
(Wikipediaより)

割り算した余りを、再利用して計算を繰り返していくイメージだ。

ユークリッド互除法を手続き的に記述すると次のようになる。

出力結果が最大公約数となる。

仕組みを視覚的に理解するには、次を参照されたい。

ユークリッド互除法をPythonで記述すると下記のようになる。
(参考情報である。)

def euclidean_algorithm(a, b):
  while True:
    if b == 0:
      return a
    surplus = a%b
    a = b
    b = surplus

def euclidean_algorithm(a, b):

while True:

if b == 0:

return a

surplus = a%b

a = b

b = surplus

さて、先程の説明を読んだ人は、ユークリッド互除法を説明できますね。
ユークリッド互除法とは何か？そして、どのような性質を利用したアルゴリズムであるか？

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

じゃあね〜〜〜。