初心者のためのアルゴリズム〜ユークリッドの互除法編〜

今回は、ユークリッドの互除法をPythonで実行していきたいと思います。
プログラミングを始める前から「ユークリッドの互除法」という言葉自体は知ってた方も多いのではないでしょうか。
高校数学IAでやりましたよね。
まずはユークリッドの互除法の説明と、その数IAで習う問題を見てみましょう！

ユークリッドの互除法とは

古代エジプトの数学者ユークリッドが記した『原論』に書かれている、世界最古のアルゴリズムとされている方法です。
2つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つことを発見し、b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となることを明示しました。（Wikipedia参考）

数IA

Q.
2077と1829の最大公約数を求めよ。

A.
2077 = 1829・1 + 248
1829 = 248・7 + 93
248 = 93・2 + 62
93 = 62・1 + 31
62 = 31・2
よって、最大公約数は31

忘れていた人もこれをみたら思い出したのではないでしょうか？
機械的に解けるので、数IAの模試でこの手の問題が出たら喜んでいました。

アルゴリズム

Euclid.py

def euclid(a, b):
     r = a % b
     while(r != 0):
         a = b
         b = r
         r = a % b
     return b

print(euclid(2077, 1829))

実際にコードを書くと、このようになります。
これを実行すると、きっちり31が最大公約数として表示されました。
Pythonを利用することで、一瞬で最大公約数を求めることができるようになりました。

まとめ

ユークリッドの互除法を理解することができたでしょうか。
コード自体は非常に簡単なので、一度書いてみるとより理解が深まるかもしれないですね。