VB常用算法（五）约数因子- -

曹苏群  http://caosuqun.bokee.com

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

解题技巧

该算法需要识记！

这种类型题目的扩展是约数和因子题型。

2、实战练习

1)        补充代码（2003春二（9））

         给定一个十进制正整数，找出小于它并与其互质的所有正整数（所谓互质数是指最大公约数为1的两个正整数，下图是程序执行画面）。

              Option Explicit

                  Private Function gcd（     （1）     ） As Integer

                    Dim r As Integer

                         r = m Mod n

                    If r = 0 Then

                          gcd = n

                    Else

                          m = n: n = r

                                        （2）    

                 End If

                  End Function

                  Private Sub Command1_Click()

                    Dim n As Integer, p As Integer

                    n = Val(Text1)

                    For p = n - 1 To 2 Step -1

                               If      （3）       Then List1.AddItem p

                          Next p

                  End Sub

2)        编程题（2002秋上机试卷01）

         生成一个三行八列的二维数组A(3,8)，其中前两行元素产生的方法是：

用初值X1=26及公式Xi+1=(25×Xi+357) Mod 1024，产生一个数列：X1、X2、......、X16 。

其中X1~X8作为A的第一行元素；X9~X16作为A的第二行元素；A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。