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

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

私有函数GCD的递归实现
ByVal m As Long，ByVal n As Long
Dim temp As Long
If m < n Then temp = m:m = n = temp
Dim r As Long
r = m Mod n
If r = 0 Then
Else
m = n
n = r

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

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

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