当前位置>>常用算法>>算法2    
返回首页  
 

 
     
 

算法2 求最大公约数算法

 
 
算法描述
求两个整数的最大公约数、最小公倍数
算法分析
 求最大公约数的算法思想:(最小公倍数=两个整数之积/最大公约数)
(1) 对于已知两数m,n,使得m>n;
(2)  m 除以n 得余数r;
(3) 若r=0,则n为求得的最大公约数,算法结束;否则执行(4);
(4) m←n,n←r,再重复执行(2)。

代码如下:
m=inputBox("m=")
n=inputBox("n=")
nm=n*m
If m < n Then t = m: m = n: n = t
    r=m mod n
    Do While (r <> 0)                               
         m=n
         n=r
         r= m mod n
    Loop
Print "最大公约数=", n
Print "最小公倍数=", nm/n