VB常用算法5约数因子.doc

VB常用算法-约数因子一、算法说明：1最大公约数：用辗转相除法求两自然数m、n的最大公约数。（1）首先，对于已知两数m、n，比较并使得mn；（2）m除以n得余数r；（3）若r0，则n为求得的最大公约数，算法结束；否则执行步骤（4）（4）mn nr 再重复执行（2）例如1： 10与5分析步骤：m=10 n=5r=m mod n=0所以n(n=5)为最大公约数例如2： 24与9分析步骤：m=24 n=9r=m mod n=6r0 m=9 n=6r=m mod n=3r0 m=6 n=3r=m mod n=0所以n(n=3)为最大公约数算法实现：1） 循环实现Private Function GCD(ByVal m As Long, ByVal n As Long) As Long Dim temp As Long Dim r As Long If m n Then temp = m: m = n: n = temp Do r = m Mod n If r = 0 Then Exit Do m = n n = r Loop GCD = nEnd Function说明：m和 n 是要求解最大公约数的两个自然数，函数的返回值是m和n的最大公约数。2）递归方法实现Private Function GCD(ByVal m As Long, ByVal n As Long) As Long Dim temp As Long Dim r As Long If m n Then temp = m: m = n: n = temp r = m Mod n If r = 0 Then GCD = n Else m = n n = r GCD = GCD(m, n) End IfEnd Function说明：m和 n 是要求解最大公约数的两个自然数，函数的返回值是m和n的最大公约数。2最小公倍数方法1： mn最大公约数方法2：Private Function LCM(ByVal X As Integer, ByVal Y As Integer) as Integer Dim M As Long, Flg As Boolean Flg = False Do Until Flg M = M + X If M Mod Y = 0 Then Flg = True End If Loop LCM = M End Function 方法3：(与方法2算法思想一致，实现代码有所不同)Private Function LCM(ByVal X As Long, ByVal Y As Long) as Long Dim I As Long FOR I=X TO X*Y STEP X If I Mod Y = 0 Then LCM=I Exit Function End If Next IEnd Function3互质数最大公约数为1的两个正整数这种类型题目的扩展是约数和因子题型。二、实战练习 例1 完善程序填空题。（2003春二（9）给定一个十进制正整数，找出小于它并与其互质的所有正整数（所谓互质数是指最大公约数为1的两个正整数，下图是程序执行画面）。Option ExplicitPrivate 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 IfEnd 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=(25Xi+357) Mod 1024，产生