歐幾里得演算法又稱輾轉相除法，是指用于計算兩個非負整數a，b的最大公約數，
假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾里得演算法，是這樣進行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公約數為1
簡單來說就是用大數除小數，然后接著將每個式子里面的除數不斷除以余數直到余數為零，那么最后的除數便是公約數，
代碼：
def gcd(x, y):
dividend = max(x,y)#被除數
divider = min(x,y)#除數
remainder = dividend % divider#余數
while True:
if remainder == 0:
break
dividend = divider
divider = remainder
remainder = dividend % divider
return divider
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/386861.html
標籤：其他
上一篇：【劍指offer】第一層
下一篇：conda常用命令