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

会计考友

算法说明
* r; _& N6 |+ L　　1) 最大公约数：
　　用辗转相除法求两自然数m、n的最大公约数。
　　(1) 首先，对于已知两数m、n，比较并使得m>n;
9 y$ L5 R/ X1 l7 ]/ \" A% {/ K　　(2) m除以n得余数r;
　　(3) 若r=0，则n为求得的最大公约数，算法结束;否则执行步骤(4)
　　(4) mßn nßr 再重复执行(2)
　　譬如： 10与5
* b2 z1 W. V7 X: K5 G1 A& x　　分析步骤： m=10 n=5
　　r=m mod n=0
) X; F' C3 t" t: S　　所以n(n=5)为最大公约数
　　24与9
2 R2 G- r3 Y/ ?　　分析步骤： 以下是引用片段：
" Z( G' F+ ?9 J' ?$ L1 j: J3 Z      m=24 n=9
  M- t% x3 y+ S　　r=m mod n=6
　　r≠0 m=9 n=6
3 z/ f9 G1 T- I8 V- U) N, E　　r=m mod n=3
6 m6 l% A2 a# T+ ?7 v3 \$ N- a! u　　r≠0 m=6 n=3
9 T" g( Q4 N, M1 E　　r=m mod n=0

　　所以n(n=3)为最大公约数
　　算法实现
　　循环实现
2 K+ W# ~: ^0 y5 Q以下是引用片段：
  j$ D. ?0 U: O/ z　　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
- ]7 V( f$ X+ B: w$ e% g/ O% y　　Do
: c3 T. d! E# J5 i　　r = m Mod n
1 _! |- R; t+ i9 f　　If r = 0 Then Exit Do
& O4 E9 K& O+ [7 O　　m = n
1 s& v1 l% f$ c, n　　n = r
+ X: X1 A4 @. w: H, C* r0 i0 E9 l  O　　Loop
5 V' a1 t/ |1 ]2 m1 c* ^" C　　GCD = n
　　End Function
" c$ ~9 A9 X" i3 y
　　递归实现
以下是引用片段：
! ~& f0 Y+ J( b　　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
% N; U/ h; v. K: z+ y: ]　　r = m Mod n
　　If r = 0 Then
　　GCD = n
　　Else
. X2 L/ O: f2 l+ h* P　　m = n
3 ^5 |  B6 V* a　　n = r
1 d: v' S& h6 N$ a  W/ [/ T　　GCD = GCD(m, n)
　　End If
　　End Function
9 y* M1 i5 Z/ o# l3 P
　　2) 最小公倍数
　　m×n÷最大公约数
　　3) 互质数
/ W/ J1 C, a6 ^2 V! Q( K　　最大公约数为1的两个正整数
+ C' P% y1 F& \% O# g$ }$ q　　解题技巧
& e/ Z* D) _7 H2 ?3 y: }　　该算法需要识记!
* M2 d. b5 I7 b' \# |　　这种类型题目的扩展是约数和因子题型。