欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数

算法思想（来自百度知道）：

首先给定两个数a,b（a>b）,则根据除法运算，a/b=q…r。q是商，r是余数。也可以表示为a=bq+r。这是小学就知道的。

下面给出一个定理： 若a=bq+r，则（a,b）=（b,r），即a,b的最大公约数等于b,r的最大公约数。

举个例子来说： 24=10*2+4，那么(24,10)=(10,4)=2

这个定理的证明也很简单。 设c是a和b的任意一个公约数,则c能同时整除a和b,即a=cx,b=cy，（x,y是整数） 将它们代入“a=bq+r”中： cx=cyq+r 得到r=c(x-yq)，说明c也能整除r，即c也是b和r的公约数。 于是a和b的公约数就是b和r的公约数，那么a和b最大公约数就是b和r的最大公约数，（a,b）=（b,r）。 定理得证。

欧几里德算法就是对照这个定理来做的，每一次辗转相除其实就是用了一次上面的定理，一步一步递推得到最后结果。

辗转相除法：

（1）比较两数，并使m>n

（2）将m作被除数，n做除数，相除后余数为r

（3）循环判断r，若r==0，则n为最大公约数，结束循环。若r ！=0 ，执行m=n，n=r；将m作被除数，n做除数，相除后余数为r

运行代码如下：

num1 = int(input("请输入第一个数字："))
num2 = int(input("请输入第一个数字："))
m = max(num1, num2)
n = min(num1, num2)
r = m % n
while r != 0:
    m = n
    n = r
    r = m % n
print(num1, "和", num2, "的最大公约数为", n)