1、算法说明 1) 最大公约数: 用辗转相除法求两自然数m、n的最大公约数。 (1) 首先,对于已知两数m、n,比较并使得m>n; (2) m除以n得余数r; (3) 若r=0,则n为求得的最大公约数,算法结束;否则执行步骤(4) (4) mßn nßr 再重复执行(2) 譬如: 10与5 分析步骤: m=10 n=5 r=m mod n=0 所以n(n=5)为最大公约数 24与9 分析步骤: m=24 n=9 r=m mod n=6 r≠0 m=9 n=6 r=m mod n=3 r≠0 m=6 n=3 r=m mod n=0 所以n(n=3)为最大公约数 算法实现 循环实现 Private Function GCD(ByVal m As Long, ByVal n As Long) As Long Dim temp As Long If m < n Then temp = m: m = n: n = temp Dim r As Long Do r = m Mod n If r = 0 Then Exit Do m = n n = r Loop GCD = n End Function
递归实现 Private Function GCD(ByVal m As Long, ByVal n As Long) As Long Dim temp As Long If m < n Then temp = m: m = n: n = temp Dim r As Long r = m Mod n If r = 0 Then GCD = n Else m = n n = r GCD = GCD(m, n) End If End Function
2) 最小公倍数 m×n÷最大公约数
3) 互质数 最大公约数为1的两个正整数
解题技巧 该算法需要识记! 这种类型题目的扩展是约数和因子题型。 首页 1 2 尾页
相关资料
|