计算机等级考试二级VB常用算法(5)：约数因子

会计考友

　　　
1、算法说明
1)        最大公约数：
         用辗转相除法求两自然数m、n的最大公约数。
（1）        首先，对于已知两数m、n，比较并使得m>n；
0 {0 x- K3 t" f（2）        m除以n得余数r；
（3）        若r＝0，则n为求得的最大公约数，算法结束；否则执行步骤（4）
/ \1 M  L+ d8 U# y4 R（4）        mßn   nßr  再重复执行（2）
譬如：      10与5
6 t* l5 E; |1 x$ f: N分析步骤：        m=10 n=5
                          r=m mod n=0
" M- b: h( f1 i) W+ ?                          所以n(n=5)为最大公约数
( _) {4 L. J: D                  24与9
分析步骤：        m=24 n=9
                          r=m mod n=6
8 L+ r2 I2 ?% r- p. {                          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)为最大公约数
% n, M; d9 G/ F6 s% _" a
算法实现
循环实现
+ e0 S% ]5 m- z' Y( t) Z7 v5 j  UPrivate Function GCD(ByVal m As Long, ByVal n As Long) As Long
. Y- @+ m$ a5 T7 s5 `    Dim temp As Long
    If m < n Then temp = m: m = n: n = temp
    Dim r As Long
    Do
$ X4 U; ^$ |& W: _7 N0 y0 u# Z+ ~        r = m Mod n
        If r = 0 Then Exit Do
        m = n
        n = r
    Loop
    GCD = n
   End Function

; E- L+ Z* a! \& Y递归实现
; D1 \1 ^4 d; _: R                  Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
4 V7 `5 A. q: Z  a    Dim temp As Long
    If m < n Then temp = m: m = n: n = temp
    Dim r As Long
5 e7 H8 p' e. G    r = m Mod n
    If r = 0 Then
9 x0 C: Q6 Z0 W3 c5 L- s2 L        GCD = n
. k" b5 M( ~5 E- K5 r: Y+ E    Else
& S' J# W+ N9 O1 M  c) I  g        m = n
1 D- w0 I) c! o" J        n = r
* T2 u: c$ F/ }% e        GCD = GCD(m, n)
    End If
                  End Function

, f. i7 ^. t0 y2 D7 t2)        最小公倍数
; Q2 w0 z3 Z# D7 W) l         m×n÷最大公约数

0 a: R- [+ f9 ]3)        互质数
) _4 t) A+ F- {0 u         最大公约数为1的两个正整数
7 G: w2 }1 g/ |. Y( S' j2 {
( J; t1 C, y1 `( O! B6 P/ ]解题技巧
3 h; C+ U1 m- `2 h8 h该算法需要识记！
这种类型题目的扩展是约数和因子题型。

会计考友

</p>　　2、实战练习
3 F( \" L: }  f
) E5 h  d4 E" g8 E7 @( N
1)        补充代码（2003春二（9））
         给定一个十进制正整数，找出小于它并与其互质的所有正整数（所谓互质数是指最大公约数为1的两个正整数，下图是程序执行画面）。
7 u1 R9 H) z) k6 ?* Z! G8 q
8 G4 T4 [- W' ~8 J/ ?; Q
/ O( X; ?+ H8 E0 s              Option Explicit
- }3 S' w# h* C' P
0 a, q7 K6 i" D% x& Q. X                  Private Function gcd（     （1）     ） As Integer
% b- Y0 d5 L* V% [, E                    Dim r As Integer
# T- M. ]  I) T. S                         r = m Mod n
/ G4 o' b% h' o                    If r = 0 Then
* r- v$ x3 f; d( J2 ^8 i2 B9 f                          gcd = n
3 _; b, s: B+ F. B  {; i/ _! ?( M                    Else
) a0 a, L+ o1 G) A) W( X7 q                          m = n: n = r
                                        （2）     
' b, D' [3 M# v1 P                 End If
                  End Function

                  Private Sub Command1_Click()
                    Dim n As Integer, p As Integer
                    n = Val(Text1)
                    For p = n - 1 To 2 Step -1
                               If      （3）       Then List1.AddItem p
                          Next p
4 M' ^7 L' C; O2 V" I* D/ D                  End Sub
2)        编程题（2002秋上机试卷01）
: x9 e9 \9 v* c9 F( [         生成一个三行八列的二维数组A(3,8)，其中前两行元素产生的方法是：
用初值X1=26及公式Xi+1=(25×Xi+357) Mod 1024，产生一个数列：X1、X2、......、X16 。
5 L$ I* E( Y; }3 _) k' F其中X1~X8作为A的第一行元素；X9~X16作为A的第二行元素；A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。