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

1.算法说明
1)公约数:用相除法求两个自然数m和n的公约数。
(1)首先，对于已知的两个数M和N，比较并使M > N；
(2)m除以n得到余数r；
(3)若r = 0，则n为公约数，算法结束；否则，步骤(4)
(4)m & szlig；n n & szligR重复(2)
例如:10和5
分析步骤:m=10 n=5
r=m mod n=0
，所以n(n=5)是公约数
24和9[/br]R≠0m = 9n = 6
R = m mod n = 3
R≠0m = 6n = 3
R = m mod n = 3

算法实现
循环实现
私有函数GCD (byval m as long，ByVal n 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则Exit Do
m = n
n = r
Loop

递归实现
私有函数GCD(ByVal m为long，ByVal n为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

2)最小公倍数
m×n÷公约数

3)两个正整数的素数公约数
为1

解题技巧
这个算法需要死记硬背！
这类题的外延是除数和因子题。

2.实践练习
1)补充代码(春二2003 (9))
给定一个十进制正整数，找出所有小于它的正整数，并与它互质(所谓互质数是指两个正整数的公约数为1，下图为程序执行画面)。
选项显式

私有函数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函数

private Sub command 1 _ Click()
Dim n为整数，p为整数
n = Val(text 1)
For p = n-1 To 2 Step-1
If(3)Then list 1。AddItem p
Next p
End Sub

2)编程题(2002年秋季计算机试卷01)
生成一个三行八列的二维数组A(3，8)，其中前两行元素由:
利用初始值X1=26和公式Xi+1=(25×Xi+357) Mod 1024生成一个序列:
其中X1~X8为A的第一行元素；X9~X16作为A的第二行元素；的第三行中的元素值取前两行中同一列中元素的公约数。最后按照图形格式显示在图片框中。