计算机二级VB常用算法：约数因子算法说明

算法说明
　　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的两个正整数
　　解题技巧
　　该算法需要识记!
　　这种类型题目的扩展是约数和因子题型。