VB中求最大公约数问题

这叫“辗转相除法”。具体原理为：

令开始的两个数分别为a，b，其中a>b，则：

我们用数a除以数b商c余d，那么a=b*c+d。
假设a，b有公约数e，则d=a-b*c也一定有约数e。
即：在每一步中，如果a÷b=c……d，则a，b的公约数一定是d的约数。

这样，在辗转相除的过程中，d的值会越来越小，但其始终是a，b的公约数e的倍数。

直到最后一步，d=0，这样前一步的“d”，也就是这一步的“b”，就是这一步“a”，“b”的最大公约数，因为“b”整除“a”。

回到开始，每一步中都有“d”是a，b的公约数e的倍数。这样就有结论：
当d最小时，d等于a，b的公约数e的一倍。

∵在计算的过程中，d的约数集包含a，b的公约数集，
∴如果d是“a”，“b”的最大公约数，则d是a，b的最大公约数e。

明白了吗？

先取得两个参数m和n，但不能确定哪个大哪个小

利用“If m
求最大公约数关键在于下边这段循环
r=m mod n
Do While (r<>0)
m=n :n=r
r=m mod n
Loop

利用“r=m mod n”使r值为m和n的余数

循环中将n值赋给m，r值赋给n，然后r再取得此时m和n的余数，直到m和n的余数为零时为止。此时n值即为所求的最大公约数。

假如以24跟10实验
m＝24，n＝10，r＝4
第一轮循环：m＝10，n＝4，r＝2
第二轮循环：m＝4，n＝2，r＝0
循环中止。

得出最大公约数为2

此时再利用开头的参数mn，即为240，mn除以最大公约数，得出的即为最小公倍数120

至于为什么这么算，我也没想太明白，大概是根据求公约数的短除法推导出来的办法吧，希望以上回答对你有帮助！

2数的最小公倍数 是 2数积除以2数最大公约数
6 * 8 =48 /2 =24
求公约数则是 用 2数中较小的数 和 2数的余数 再去求余数 直到没余数为止
此时最后一个余数就是 最大公约数
其实都是数学问题 现实中我们如何求 基本上VB代码就是按这个思路去做的

29和17都是质数也是素数，所以他们的公约数就是1喽，因为各自除了本身和1外没有约数

最大公约数就是 1 啊~

这是欧几里德算法