Posted on 2007-04-02 22:55
大大毛 阅读(399)
评论(0) 编辑 收藏 所属分类:
常用算法
最近用到最小公倍数、最大公约数是因为需要对用户 Key In 的数据（分数形式）进行检验，检验的规则是同组的数据之和 = 1，这样就需要求分母的最小公倍数。
在网上搜索了一下，主要介绍的算法有两种：
1. 欧几里德算法
又叫辗转相除法，是最常用的算法，以前学到的就是这个了。它仅在对大素数的模运算时会遇到麻烦。
'
Euclid算法（VB）
Public
Function
fEuclid(lngNum1
As
Long
, lngNum2
As
Long
)
As
Long
Dim
lngA
As
Long
,lngB
As
Long
,lngC
As
Long
If
lngNum1
=
0
Or
lngNum2
=
0
Then
If
lngNum1
=
0
Then
fEuclid
=
lngNum2
Else
fEuclid
=
lngNum1
End
If
Exit
Function
End
If
If
lngNum1
>=
lngNum2
Then
lngA
=
lngNum1:lngB
=
lngNum2
Else
lngA
=
lngNum2:lngB
=
lngNum1
End
If
lngC
=
lngA
Mod
lngB
Do
While
lngC
>
0
lngA
=
lngB:lngB
=
lngC
lngC
=
lngA
Mod
lngB
Loop
fEuclid
=
lngB
End Function
2. Stein算法
a. 如果A=0，B是最大公约数；如果B=0，A是最大公约数
b. An = A，Bn = B，Cn = 1 （当n=1时）
c1. 如果An和Bn都是偶数，则An+1 = An /2，Bn+1 = Bn /2，Cn+1 = Cn *2
c2. 如果An是偶数，Bn不是偶数，则An+1 = An /2，Bn+1 = Bn ，Cn+1 = Cn
c3. 如果Bn是偶数，An不是偶数，则Bn+1 = Bn /2，An+1 = An ，Cn+1 = Cn
c4. 如果An和Bn都不是偶数，则An+1 = |An - Bn|，Bn+1 =min(An,Bn)，Cn+1 = Cn
d. n++
Stein算法最大的好处就是它只使用到了减法以及移位操作（与2运算），能够避免欧几里德算法运用到大数上所面临的问题。
'
Stein算法（VB）
Public
Function
fStein(lngNum1
As
Long
, lngNum2
As
Long
)
As
Long
Dim
lngResult
As
Long
, lngA
As
Long
, lngB
As
Long
, lngC
As
Long
lngA
=
lngNum1: lngB
=
lngNum2: lngC
=
1
Do
While
lngA
<>
0
And
lngB
<>
0
If
lngA
Mod
2
=
0
And
lngB
Mod
2
=
0
Then
lngA
=
lngA
/
2
: lngB
=
lngB
/
2
: lngC
=
lngC
*
2
Else
If
lngA
Mod
2
<>
0
And
lngB
Mod
2
<>
0
Then
If
lngA
>
lngB
Then
'
lngB = lngB
lngA
=
lngA
-
lngB
Else
lngB
=
lngA
lngA
=
lngB
-
lngA
End
If
Else
If
lngA
Mod
2
=
0
Then
lngA
=
lngA
/
2
Else
lngB
=
lngB
/
2
End
If
End
If
End
If
Loop
If
lngA
=
0
Then
lngResult
=
lngC
*
lngB
Else
lngResult
=
lngC
*
lngA
End
If
fStein
=
lngResult
End Function
最小公倍数 = M * N / 最大公约数