最大公约数

题目

求两个数的最大公约数

解法

在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求取最大公约数的一种算法。辗转相除法首次出现于欧几里得的《几何原本》中的第Ⅶ卷，书中的命题ⅰ和命题ⅱ所描述的就是辗转相除法，而在中国，辗转相除法最早出现在《九章算法》中。

辗转相除法之所以有效是因为其基于一个核心原理，即：

两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

为了更容易理解，可以对这句话进行简单的分析，然后可以对其进行改写，使之更容易理解。

首先根据此描述，可以先确定这是一个等式，即（）= （） ，然后再将相应的值填入括号中，就可以直接列出如下等式：GCD（较大数，较小数）= GCD（较小数，二者余数）；紧接着可以对其进行进一步的改写，将其改写为GCD（被除数，除数） = GCD（除数，余数）（这里的GCD就是辗转相除算法），这样理解起来会更加容易。

假设我们有两个数字[12921，4234]。我们将两数中较大的那一个看作是被除数A，将较小的那一个看作是除数B，二者相除的商记作C，余数记作D。这样我们就可以得到一个等式：A = B×C + D。而辗转相除法的所要用到的原理则是：(A , B) = (B , D)。有了这个公式我们就可以进行计算了，最后算出答案是73。

详细的计算过程是这样的：

\((12921，4234) = (4234, 219) \\ (4234, 219) = (219, 73) \\ (219, 73) = (73，0)\) 最后就可以得到73是最终的结果，也就是二者的最大公约数。

public class Solution {

    public void gcd(int n1, int n2) {
        
    }

}