计算机等级考试二级VB常用算法：约数因子

　　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) 补充代码

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

　　VB src="/upload/2007-4-7/20074711381878082.jpg" width=288>

Word-WRAP: break-word" bgColor=#f3f3f3>以下是引用片段： 　　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) 编程题

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

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

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