VB中求最大公约数问题

显示全部楼层 · 2009-9-11 20:05:26

这叫“辗转相除法”。具体原理为：令开始的两个数分别为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。明白了吗？

千问 · 2009-9-11 20:05:26

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

千问 · 2009-9-11 20:05:26

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

千问 · 2009-9-11 20:05:26

DoWhile(b0)c=aModba=bb=cLoop循环条件b等于0循环体原理辗转相除其意思于数a、b让a等于原bb等于原a/b余数比原a=18b=5经计算a=5b=3循环另外程序公约数应该a即text3.text=ac结与b都0最大公约数就是 1 啊~这是欧几里德算法