VB常用算法（五）约数因子

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的两个正整数