1) 最大公約數(shù)：
用輾轉(zhuǎn)相除法求兩自然數(shù)m、n的最大公約數(shù)。
（1） 首先，對(duì)于已知兩數(shù)m、n，比較并使得m>n；
（2） m除以n得余數(shù)r；
（3） 若r＝0，則n為求得的最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟（4）
（4） mßn nßr 再重復(fù)執(zhí)行（2）
譬如： 10與5
分析步驟： m=10 n=5
r=m mod n=0
所以n(n=5)為最大公約數(shù)
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)為最大公約數(shù)
算法實(shí)現(xiàn)
循環(huán)實(shí)現(xiàn)
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
遞歸實(shí)現(xiàn)
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) 最小公倍數(shù)
m×n÷最大公約數(shù)
3) 互質(zhì)數(shù)
最大公約數(shù)為1的兩個(gè)正整數(shù)
解題技巧
該算法需要識(shí)記！
這種類型題目的擴(kuò)展是約數(shù)和因子題型。
2、實(shí)戰(zhàn)練習(xí)
1) 補(bǔ)充代碼（2003春二（9））
給定一個(gè)十進(jìn)制正整數(shù)，找出小于它并與其互質(zhì)的所有正整數(shù)（所謂互質(zhì)數(shù)是指最大公約數(shù)為1的兩個(gè)正整數(shù)，下圖是程序執(zhí)行畫(huà)面）。
Option Explicit
Private Function gcd（ （1） ） As Integer
Dim r As Integer
r = m Mod n
If r = 0 Then
gcd = n
Else
m = n: n = r
（2）
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
End Sub
2) 編程題（2002秋上機(jī)試卷01）
生成一個(gè)三行八列的二維數(shù)組A(3,8)，其中前兩行元素產(chǎn)生的方法是：
用初值X1=26及公式Xi+1=(25×Xi+357) Mod 1024，產(chǎn)生一個(gè)數(shù)列：X1、X2、......、X16 。
其中X1~X8作為A的第一行元素；X9~X16作為A的第二行元素；A的第三行元素值取前兩行同列元素的最大公約數(shù)。最后按圖示格式顯示在圖片框中。
