欧几里得算法（脑补链接）求最大公约数（Python）

欧几里得算法又称辗转相除法，是指用于计算两个非负整数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