计算机等级考试二级VB算法(5)：约数因子

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、算法说明

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的两个正整数

解题技巧
该算法需要识记！
这种类型题目的扩展是约数和因子题型。