解答例_3_14

解答例：練習問題_3_14（最大公約数② 素因数分解を参考に）

import time

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

x_start = 2
g = 1

while True:

    for x in range(x_start, min(a, b) + 1): 
        counter += 1
        if (a%x == 0) and (b%x == 0):
            a, b, x_start = a//x, b//x, x
            g *= x
            break  # for文のbreak

    else: # 公約数を持たない整数同士が残った場合
        break  # while文のbreak

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

g: 4242763
run time: 0.017847061157226562 s
counter: 86588

確認はこちらもgが一致していればOKです。
カウンター(counter)の回数は①に比べ 86588/29699341 = 約0.29% となり実行時間も0.017847/2.3955 = 約0.75% とかなり減っています。

但し、これは a と b に入力する値によって減り方が変わります。例えば大きさが同じくらいの
a, b = 46670399, 29699507 (共に素数)
を入力してみると、最大公約数(g)は１で、カウンターはほぼ同じですが、実行時間は筆者のPC上で①の場合 3.68秒 ②では 3.83秒と若干②が多くなっています。だからと言って今回の②のコード改良が無意味と言うことはできませんが、それぞれの特徴は把握しておくべきかと思います。