计算机二级VB常用算法：约数因子算法说明

会计考友

算法说明
　　1) 最大公约数：
3 k+ S5 L2 B1 l* Q　　用辗转相除法求两自然数m、n的最大公约数。
　　(1) 首先，对于已知两数m、n，比较并使得m>n;
/ C2 O- z# M, X8 @! [% T  l　　(2) m除以n得余数r;
　　(3) 若r=0，则n为求得的最大公约数，算法结束;否则执行步骤(4)
; ~3 A% V& F; I, d; F. i; r　　(4) mßn nßr 再重复执行(2)
　　譬如： 10与5
3 N9 H& s9 r! c: D1 R　　分析步骤： m=10 n=5
' n5 \, I) P. j$ V+ L　　r=m mod n=0
　　所以n(n=5)为最大公约数
　　24与9
! m3 W, [) I) c% X+ g- C　　分析步骤： 以下是引用片段：
      m=24 n=9
　　r=m mod n=6
2 x' {0 S" Z, |6 N$ Y　　r≠0 m=9 n=6
　　r=m mod n=3
　　r≠0 m=6 n=3
" j6 U: ]1 o/ A- c3 E　　r=m mod n=0

; B. _( w, `7 V, J! h, W　　所以n(n=3)为最大公约数
　　算法实现
　　循环实现
  h) m  M8 D7 I8 `. j以下是引用片段：
　　PRivate Function GCD(ByVal m As Long, ByVal n As Long) As Long
　　Dim temp As Long
: T% j1 F1 @2 s/ N* E# e' Q4 Q　　If m < n Then temp = m: m = n: n = temp
& r+ g* X6 N2 i: f( @$ ^+ N3 |3 m　　Dim r As Long
1 O4 A. _" Q$ e- U0 I　　Do
　　r = m Mod n
　　If r = 0 Then Exit Do
$ A- ]" @& G( p% N( @　　m = n
　　n = r
　　Loop
: y* K- z3 S0 n$ g" D0 ?  B　　GCD = n
: G% t: X9 y! [) G0 M5 c　　End Function

7 h, @  d' @1 s( s- T) V1 L" E　　递归实现
# W9 A. J- e4 s* `1 W! i6 b/ `* d以下是引用片段：
5 e1 j" a# G4 c　　Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
　　Dim temp As Long
2 Q5 L* S% R( o& B! K" S; f　　If m < n Then temp = m: m = n: n = temp
, F, Z# b8 `& I* C% l7 [　　Dim r As Long
　　r = m Mod n
　　If r = 0 Then
　　GCD = n
- z, \' u5 t5 d4 e) D　　Else
' ?; e9 G9 _, e& j* J! b- v7 W　　m = n
　　n = r
　　GCD = GCD(m, n)
7 k; M2 Y; l- d5 P; y　　End If
* G; t- c' O3 U- l5 b. t　　End Function
) |+ R$ _4 n: A5 i9 M3 v
7 ^# w- X1 n) F9 R+ M　　2) 最小公倍数
9 \0 S. ^6 b! d9 {* o) }　　m×n÷最大公约数
　　3) 互质数
　　最大公约数为1的两个正整数
　　解题技巧
　　该算法需要识记!
5 n8 d) ^0 S9 Z, L$ @; |, Z& ?! L7 J　　这种类型题目的扩展是约数和因子题型。