Pythonで最大公約数を求めるには

Pythonを使用して最大公約数を取得するには次の2つの方法があります。

方法①：ループ処理を用いる

def gcd(a, b):
while b:
a, b = b, a % b
return a
x = int(input("请输入第一个数："))
y = int(input("请输入第二个数："))
print("最大公约数是：", gcd(x, y))

2番目の方法: 再帰的方式を使用します。

def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
x = int(input("请输入第一个数："))
y = int(input("请输入第二个数："))
print("最大公约数是：", gcd(x, y))

いずれの方法も、最大公約数を求める際にユークリッドの互除法を利用しています。1つめの方法は繰り返し処理をもちいていて、每次bに小さい数、aに大きい数の剰余を代入し、bが0になるまで行います。2つめの方法は再帰を利用していて、小さい数を1つめの引数、大きい数の剰余を2つめの引数とし、2つめの引数が0になるまで行います。