求两个数的最大公约数 公约数是怎么算出来的

一、如何求两数的最大公约数

要求两个数的最大公约数，可以使用欧几里得算法。首先，将两个数中较大的数除以较小的数，得到余数。然后，将较小的数作为被除数，余数作为除数，再次进行相除，依次循环直到余数为0。此时，被除数就是这两个数的最大公约数。这个算法的时间复杂度为O(logn)，效率非常高。通过这种方法，可以轻松地求出两个数的最大公约数。

二、两个数求最大公约数公式是什么

算最大公约数有个技巧，就是10以内算法，我只知道一个不算最直观的算法，你看看可不可以:

以你给的两个数为例，首先两个数尾数都是5，说明都可以被5整除，那就两个数同时除以5，

如果尾数都为偶数则被2整除，尾数为0，则是被10整除，依次类推，两个0就是100，先找到最容易看到的数据.

1125÷5=225,855÷5=171，

其次，225和171不是那么容易看出来，则看看是不是被9或3整除，这里有个窍门，就是一个数是不是能被9和3整除，这个数各个位数上的数字相加，相加后的数字如果能被9和3整除，则这个数可以被9和3整除。2+2+5=9,1+7+1=9明细看出，都可以被9整除，

225÷9=25,171÷9=19，

最后，19位质数，没法约分，则得出结论1125和855最大公约数为5×9=45

三、两个数的最大公约数

最大公约数又叫最大公因数，是指两个或多个整数共有约（因）数中最大的一个。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。