(辗转相除法) 求2个数的最大公约数
本帖最后由 无理想的闲鱼 于 2024-11-3 00:17 编辑先看一个视频： 欧几里得演算法(辗转相除法)_哔哩哔哩_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='')
{:7_113:}
页:
[1]