解答例_3_15

解答例：練習問題_3_15（最大公約数③ ユークリッド互除法）

以下はwhile文を使った場合の解答例です。

import time

a, b = 46670393, 29699341
t_start = time.time()
counter = 0

while b:
    a, b = b, a%b
    counter += 1

g = a
        
print('g: ', g)
print('run time:', time.time() - t_start, 's')
print('counter: ', counter)

g: 4242763
run time: 0.0011470317840576172 s
counter: 4

こちらもgが一致していればOKです。
カウンター(counter)の回数は4回、実行時間は1.1ms(1.1ミリ秒=0.0011秒)と劇的に減っています。
②で試した共に素数である a, b = 46670399, 29699507 を試した場合でも、カウンターは12回、実行時間は1.1msです。

代入値	① 単純な割り算	② 素因数分解風	③ ユークリッド互除法
a = 46670393 (7x7x11x86587) b = 29699341 (7x7x7x86587)	2.4s	18ms	1.1ms
a = 46670399 (素数) b = 29699507 (素数)	3.7s	3.8s	1.1ms

以上、数学的手法を用いてアルゴリズムを単純化することにより、計算の高速化が可能となる例として最大公約数を取り上げてみました。
③は実際には while b: と a, b = b, a%b の二行で最大公約数を計算していることになります。この箇所は良く使われている最大公約数を求めるコードの一つです、この二行は無駄の無いシンプルでわかり易いコードと言えます。

互助法を考えたユークリッドさんは紀元前３世紀ごろの古代エジプトの方で、「幾何学の父」とも称されているそうですが、その偉大さの一端をこの問題で感じることができます。