Question

用辗转相除法求两数的最小公倍数和最大公约数 VB

Private Sub Command1_Click()
m = InputBox("输入第一个自然数")
n = InputBox("输入第二个自然数")
（1）
Do While （2）
m = n
(3)
r=m mod n
Loop
Print "最大公约数为：";n
End Sub
(1)(2)(3)是啥

Answer 1

设两数为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)。

Answer 2

设两数为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)。

Answer 3

int hcf(int u,int v)
{
int a,b,t,r;
if(u>v){t=u;u=v;v=t;}//比较2个参数大小,如果第一个数大于第二个数则交换
a=u;b=v;
while((r=b%a)!=0)
{b=a;a=r;}
return a;
}