計算機(jī)等級考試二級VB常用算法(5)：約數(shù)因子

1、算法說明

1)        最大公約數(shù)：
         用輾轉(zhuǎn)相除法求兩自然數(shù)m、n的最大公約數(shù)。
（1）        首先，對于已知兩數(shù)m、n，比較并使得m>n；
（2）        m除以n得余數(shù)r；
（3）        若r＝0，則n為求得的最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟（4）
（4）        mßn   nßr  再重復(fù)執(zhí)行（2）
譬如：      10與5
分析步驟：        m=10 n=5
                          r=m mod n=0
                          所以n(n=5)為最大公約數(shù)
                  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)為最大公約數(shù)

算法實現(xiàn)
循環(huán)實現(xiàn)
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

遞歸實現(xiàn)
                  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)        最小公倍數(shù)
         m×n÷最大公約數(shù)

3)        互質(zhì)數(shù)
         最大公約數(shù)為1的兩個正整數(shù)

解題技巧
該算法需要識記！
這種類型題目的擴(kuò)展是約數(shù)和因子題型。

希望與更多計算機(jī)等級考試的網(wǎng)友交流，請進(jìn)入計算機(jī)等級考試論壇

更多信息請訪問：考試吧計算機(jī)等級考試欄目