(辗转相除法) 求2个数的最大公约数

无理想的闲鱼

先看一个视频： 欧几里得演算法(辗转相除法)_哔哩哔哩_bilibili

运用铺瓷砖的想法，把两个数看作长方形的长和宽，运用多大的正方形瓷砖能铺满整个长方形地面

①第一次铺瓷砖，用以短边为边长(b = 6)的正方形瓷砖铺，

   16 % 6 = 4，剩下6*4的地面未铺

第一次

————————————————————————————————————————————————————————————————————————————————————————

②第二次铺瓷砖，用以短边为边长(b = 4)的正方形瓷砖铺，

   6 % 4 = 2，还有4*2的地面未铺

第二次

———————————————————————————————————————————————————————————————————————————————————————

③第三次铺瓷砖，用以短边为边长(b = 2)的正方形瓷砖铺，

   4 % 2 = 0，地面全部铺完!

第三次

那么! 16*6的地面 用(最大)边长为2的瓷砖就能铺满，所以16和6的最大公因数是2！！！

（另一种思路：也就是一直割大正方形直到找出最小的那个正方形）

归纳：第一次没有余数，最大公因数是较小的那个数

第一次有余数，步骤就是除数除以余数，重复直至整除，最后的除数就是最大公因数

a = eval(input("请输入第一个数："))
b = eval(input("请输入第二个数："))
c = a % b
while c != 0:
    a = b
    b = c
    c = a % b
print("a和b的最大公约数为：", b, sep='')

很cool的阳