求两个整数m和n的最大公约数

最大公约数(简写为gcd)是指能同时除两个或两个以上给定整数的最大正整数。

求最大公约数是数论中的一个基本问题，广泛应用于计算机科学、信息学、密码学等领域。求两个整数m和n的最大公约数的方法有很多，下面是两种常用的方法:

1，辗转减法:辗转减法是古希腊数学家欧几里得提出的一种求最大公约数的方法。具体操作如下:

首先比较M和N的大小，将较大的赋给A，较小的赋给B；计算a和b的差，赋给t；如果t等于0，那么b就是最大公约数；如果t不等于0，用(a，t)代替原来的(a，b)，然后重复2~4步，直到t等于0。折腾减法的时间复杂度为O (n 2)，在处理大数时效率很低。

2.换相除法:换相除法是一种基于欧几里德定理推论的求最大公约数的算法，也称为欧几里德算法。欧几里德算法的核心思想是利用余数的递归使原问题不断约化，原问题的解等价于约化问题的解。具体操作如下:

比较m和n，用较大的数除以较小的数，得到商q和余数r；如果r等于0，较小的数就是最大公约数；

如果r不等于0，用较小的数和余数r继续进行上述运算，直到余数为0，此时较小的数为最大公约数。相除的时间复杂度为O(log n)，在处理大数时效率较高。

综上所述，可以用两种方法求两个整数m和n的最大公约数，即折腾减法和折腾除法。但需要注意的是，这两种方法计算极大数的时间可能会比较长，所以通常需要更高效的算法来解决这个问题。