用辗转相除法求两个正整数的最大公约数

初中的时候我们学过用辗转相除法求最大公约数，今天用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