例412用辗转相除法求两自然数m,m的最大公约数和最小公倍数。 分析:求最大公约数的算法思想: (1)对于已知两数m,n,使得mn; (2)m除以n得余数r; (3)若r=0,则n为最大公约数结束;否则执行(4); (4)mn,n←,再重复执行(2)。 辗转相减法 一例:求m=14n=6的最大公约数 m=m-n m If m<n then t=m: m=n: n=t r=m mod n n=n-m nn>m Do While(r<>0) m、n为公约数m=n m=n n=r r= m mod n Do While m <>n 146 L If m >n the oop 86 Print"最大公约数=",n m=m-n 261 dan/Else 24 m. n n=n-m 1462 End ifs 620 Loop例4.12用辗转相除法求两自然数m，n的最大公约数和最小公倍数。 分析：求最大公约数的算法思想： (1)对于已知两数m，n，使得m>n； (2) m除以n得余数r； (3)若r=0，则n为最大公约数结束；否则执行(4)； (4)mn，nr，再重复执行(2)。 例 :求 m=14 ,n=6 的最大公约数. 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 m n r 14 6 2 6 2 0 m=m-n m>n n=n-m n>m m、n为公约数 m=n 辗转相减法 Do While m <> n If m > n Then m = m - n Else n = n - m End If Loop m n 14 6 8 6 2 6 2 4 2 2