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

分析步骤: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)是一个公约数。

算法实现

循环实现

私有函数GCD(ByVal m为Long，ByVal n为Long)为Long

Dim temp As Long

如果m < n，则temp = m: m = n: n = temp

Dim r一样长

做

r = m Mod n

如果r = 0，则退出Do

m = n

n = r

循环

GCD = n

结束函数

递归实现

私有函数GCD(ByVal m为Long，ByVal n为Long)为Long

Dim temp As Long

如果m < n，则temp = m: m = n: n = temp

Dim r一样长

r = m Mod n

如果r = 0

GCD = n

其他

m = n

n = r

GCD = GCD(m，n)

结束If

结束函数

2)最小公倍数

m×n÷公约数

3)质数

公约数为1的两个正整数