描述

Given two numbers, number a and number b. Find the greatest common divisor of the given two numbers.

• In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

样例

Given a = 10, = 15, return 5.

Given a = 15, b = 30, return 15.

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。另一种求两数的最大公约数的方法是更相减损法。

public class Solution {    /**     * @param a: the given number     * @param b: another number     * @return: the greatest common divisor of two numbers     */     public int gcd(int a, int b) {            // write your code here                        if(b == 0) {                return a;            }            return gcd (b, a%b);                    }}