多个数的  最大公约数、最小公倍数VB程序

我想在网页上找一个计算“多个个数”的最大公约数与最小公倍数的计算机程序，但没有找到。

有VB、C语言、pascal语言的程序，但都是只算两个数的。我就不得不自己动手了。无奈只懂一点VB，所以只能编VB的。

最大公约数与最小公倍数的求法，一般认为有四种：枚举法、短除法、质因数分解法、辗转相除法。

“枚举法”、“短除法”算两三个小数值的数还方便，但数一多、且数值很大时，就不简单了。首先要作质数的判断，或者先列一张质数表(但列到多大呢？又没法预料)，再一个个试除。所以用这个方法编程，这就很麻烦，放弃了。

“质因数分解法”也很麻烦。虽然我有一个求质因数的程序可以引用上，但分解出质因数后，又要判断这多个数的各质因数中，那些是共有的、那些是非共有的、那些是指数最低的，那些是指数最高的，要一一作排序、比有无、比大小，也很烦琐，不知要编多长，也叫人看不懂，过了一段时间，甚至连自己都看不明白了。又放弃。

最后是“辗转相除法”。太好了。

一、不论遇到什么数，不需要作“被质数整除”的判断或试除。

二、“辗转相除法”算法简单，用一个取余数的运算符号Mod，如r = A Mod B ，就可计算出A ÷ B后的余数r 。取余后，就与前面的除数B相除 (大÷小) ，再取余，再相除，步步迭代循环，直到余数r＝0为止，最后的B，就是最大公约数(A、B)=X。再利用X算出最小公倍数〔A、B〕=Y=A×B÷X。这正是“辗转相除法”的核心算法。算法单纯，且已有解算两个数的现存程序可以参考引用。所以就用“辗转相除法”来编程。

三、可以用两段相似的算法，先后得到最大公约数X与最小公倍数Y。

1  为什么要两段分开算呢？因为：当只有两个数A、B时，有最大公约数(A、B)=X、最小公倍数〔A、B〕=Y、A×B=X×Y这三个基本公式。所以Y=A×B÷X，便可顺手得到，不必再单独算了，同时得到X、Y。

但当个数超过两个时，如A、B、C、D，有(A、B、C、D)=X、但A×B×C×D ≠ X×Y，因此最小公倍数〔A、B、C、D〕=Y，要独立计算才行。

2  为什么有相似的算法呢？

用“辗转相除法”求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。有：

(A、B)=x1  →  (x1、C)=x2   →  (x2、D)=X   即 (A、B、C、D)＝X、

同样：

用“辗转相除法”求几个数的最小公倍数，可以先求出其中任意两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个数为止。最后所得的那个最小公倍数，就是所有这些数的最小公倍数。有：

(A、 B) ＝S   →〔A、B〕＝ A×B÷S ＝ y1   →

(y1、C) ＝T   →〔y1、C〕＝y1×C÷T ＝ y2   →

(y2、D) ＝U  →〔y2、D〕＝y2×D÷U ＝ Y    →   即〔A、B、C、D〕＝Y，

 

计算最大公约数与最小公倍数时，其中调换的数据X1、Y1、X2、Y2不同，但取余的循环是相同的，所以算法相似。说明到此。请看程序：

 

多个数的  最大公约数、最小公倍数VB程序

Private Sub Form_Click()

Form1.Width  = 11520                              视窗宽

Form1.Height  = 15360                             视窗高

Dim A(20)                                                  数组说明

Dim Y(20)

P = InputBox  ("输入个数P =")

For I = 1 To P

   A(I) = InputBox  ("输入A(I)=")             A用来算最大公约数X的

Next I

For I = 1 To P

   Y(I) = A(I)                                             Y用来算最小公倍数Y的

Next I

For I = 1 To P – 1                                   开始算最大公约数X

   n1 = A(1)

   m1 = A(2)

If m1 > n1 Then

m = m1: N = n1

Else

m = n1: N = m1                                          M为大数  N为小数

End If

Do

R = m Mod N                                            大数÷小数，取余数R

If R = 0 Then Exit Do                                 余数R=0  即退出循环

m = N

N = R                                                           N是最大公约数

Loop

Print Spc (4); n1; "  与  "; m1; " 的最大公约数X ="; N

 A(1) = N                                                    准备下一轮计算  A(1)=X1  X2 …

 A(2) = A(I + 2)                                                                   A(2) = C  D  …

Next I

Print Spc (4); "成功"

For I = 1 To P – 1                                          开始算最小公倍数Y

   n1 = Y(1)                                                       以下情况同上述

   m1 = Y(2)

If m1 > n1 Then

m = m1: N = n1

Else

m = n1: N = m1

End If

Do

R = m Mod N

If R = 0 Then Exit Do

m = N

N = R

Loop

B = m1 * n1 / N                                                                  B是最小公倍数

Print Spc (4) ; n1; "  与  "; m1; " 的最小公倍数Y= "; B

 Y(1) = B                                                                               准备下一轮计算  Y(1)=Y1  Y2 …

 Y(2) = Y(I + 2)                                                                                              Y(2) = C  D  …

Next I

Print Spc (4) ; "又成功"

 Print Spc (4) ; "O K"

Print

End Sub

 

算例  视窗输入   P＝4   A(1) 至A(4) ＝   8712   594   324   3744  ↙

 

视窗显示结果：

8712 与 594   的最大公约数X＝198   

198  与 324   的最大公约数X＝18

18   与 3744  的最大公约数X＝18

成功

 

8712   与 594   的最小公倍数Y＝26136

26136  与 324   的最小公倍数Y＝78408

78408  与 3744  的最小公倍数Y＝4077216

又成功

O K

 

最终：

8712   594   324  3744   的最大公约数X＝18

8712   594   324  3744   的最小公倍数Y＝4077216