！！！用辗转相除法写出求两个自然数的最大公约数

辗转相除法 是高一数学必修课程序部分的内容

简单的想法
　　设两数为a、b(b＜a)，求它们最大公约数(a，b)的步骤如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。
原理及其详细证明
　　设两数为a、b(b＜a)，用gcd(a,b)表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r)。 　　第一步：令c=gcd(a,b)，则设a=mc，b=nc 　　第二部：根据前提可知r =a-kb=mc-knc=(m-kn)c 　　第三部：根据第二步结果可知c也是r的因数 　　第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】 　　从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。 　　证毕。

程序： 　　
INPUT m,n 　　
DO 　　
r=m MOD n 　　
m=n 　　
n=r 　　
LOOP UNTIL r=0 　　
PRINT m 　　
END

INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END

用VB很快可求啊