初中的时候我们学过用辗转相除法求最大公约数，今天用Python来实现这个功能。
一、 问题描述
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：
用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
二、 代码实现原理讲解
-
step1: 将两数中大的那个数放在m中，小的放在n中。
-
step2: 求出m被n除后的余数r。
-
step3: 若余数为0则执行步骤(7)，否则执行步骤(4)。
-
step4: 把除数作为新的被除数；把余数作为新的除数。
-
step5: 求出新的余数r。
-
step6: 重复步骤(3)到(5)。
-
step7: 输出n，n即为最大公约数。
三、 Python程序实现
1 Python代码
m,n = map(int,input("请输入两个数：").split(",")) #输入两个数用逗号分开
if m<n: #如果m比n小，互换m和n的位置
m,n = n,m
r = m%n #求出m除n的余数
while r: #如果余数不为0，进行循环
m=n #把n赋值给m
n=r #把r赋值给n
r = m%n #求余数
print(f"最大公约数是{n}") #输出n，即为最大公约数
代码解析：
m,n: 先用split函数把输入用逗号分隔的两个数分离，再用map函数把分离的两个数变成整数，最后分别赋值给m和n。
if: 在后面的代码中 m作为被除数，要比n大，所以如果m小于n，则交换m和n的值(Python中不用第三个变量作为中间变量，可直接用上述语句进行变量间值的交换)。
while: 如果余数不为0，则把n赋值给m，r赋值给n，算出新的余数，直到余数变为0，程序结束，得到的n即为最大公约数。
print: 打印出最大公约数。
2 实例
实例一：
124668,3456668 #输入两个数
得到结果：
最大公约数是4
实例二：
128,48 #输入两个数
得到结果：
最大公约数是16
你可能感兴趣：
喜欢这篇文章
就请点个 “ 在看”吧
