# Python TQC考題508 最大公因數
“””
維基百科:
計算時,先將48除以18得到商2、餘數12,然後再將18除以12得到商1、餘數6,再將12除以6得到商2、餘數0,即得到最大公因數6。我們只關心每次除法的餘數是否為0,為0即表示得到答案。
(48,18)=(x,y) #初始值x=48, y=18 != 0
48%18=12
18%12=6
12%6=0
最大公因數6
先下遞迴結束的條件
餘數y==0時,return x(除數)
“””
def compute(x,y):
if y==0:
return x
else:
return compute(y,x%y)
x=eval(input())
y=eval(input())
print(compute(x,y))
#遞迴太玄
x=eval(input()) #例如:12
y=eval(input()) #例如:8,最大公因數為4
if x>y:large=x
else: large=y
for i in range(large,0,-1):
if x%i==0 and y%i==0:
print(i)
break #求到最大公因數便跳出迴圈
#沒有break的話,
#會繼續算更小的公因數
#其實題目要輸入x,y
#不是分兩次輸入
# x,y=eval(input())
#練習用遞迴寫:
近期留言