最大公因数(GCD)详解：概念、求解方法及应用

最大公因数（Greatest Common Divisor），简写为GCD，又称最大公约数，指两个或多个整数共有约数中最大的一个。

若求m和n的最大公因数，可以先将m和n分解成质因数的乘积，然后求它们的公因数，即两个数的公因数等于它们各自因子的交集。

比如求6和18的最大公因数：

6=2×3，18=2×3×3

他们的公因数就是2×3=6，所以6和18的最大公因数是6。

最大公因数的计算也可以使用辗转相除法，即用其中较大的数除以较小的数，再用除数除以出现的余数，直到余数为0。所得的最后一个除数即为所求的最大公因数。

比如求6和18的最大公因数，可以这样求：

18÷6=3，余0，最大公因数为6。