概要
ユークリッドの互除法を実装してみます。
ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
ユークリッドの互除法 – Wikipedia
サンプルコード
def euclidean_algorithm(a: int, b: int) -> int:
while b:
a, b = b, a % b
print("a", a, ", b", b)
return a
def euclidean_algorithm_recursive(a: int, b: int) -> int:
print("a", a, ", b", b)
return a if b == 0 else euclidean_algorithm_recursive(b, a % b)
print(f"euclidean_algorithm(8177, 3315) = {euclidean_algorithm(8177, 3315)}")
print(
f"euclidean_algorithm_recursive(8177, 3315) = {euclidean_algorithm_recursive(8177, 3315)}")
実行結果（例）
a 3315 , b 1547
a 1547 , b 221
a 221 , b 0
euclidean_algorithm(8177, 3315) = 221
a 8177 , b 3315
a 3315 , b 1547
a 1547 , b 221
a 221 , b 0
euclidean_algorithm_recursive(8177, 3315) = 221
