题解 | #最大公约数#

这条算法基于一个定理：两个正整数a和b(a>b) 他们的最大公约数等于a除以b的余数c和b之间的最大公约数 比如 10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    /**
    *
    *这条算法基于一个定理：两个正整数a和b（a>b）
    * ，它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
   *  比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数。
    */
    public int gcd (int a, int b) {
        // write code here
        int big = a>b?a:b;
        int small = a<b?a:b;
        if(big%small == 0){
            return small;
        }
        return gcd(big%small,small);
    }
}