题解 | #最大公约数#

我们用辗转相除法（又称欧几里得算法）来计算两个数的最大公约数 (Greatest Common Divisor)所以下文用gcd(a,b)表示a和b的最大公约数。

先举一个例子：
假如需要求 434 和 652 的最大公约数,用欧几里得算法，是这样进行的：
434 / 652 = 0 (余 434)
652 / 434 = 1(余218)
434 / 218 = 216(余2)
216 / 2 = 108 (余0)
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 434 和 652 的最大公约数 2。

算法的核心其实是 ： （即： 和 的最大公约数等于 和 的最大公约数。这个性质在本文最后会给出证明）
然后我们考虑，对于两个数 ， 如果 的话,那这两个数的最大公约数是
这样的话代码我们就可以直接写出来了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {

        if (a%b == 0) {
            return b;
        }

        return gcd(b, a%b);
    }
}