1.2 欧几里得最大公约数算法

  欧几里德法，求最大公约数的核心算法是，两个数的最大公约数，等于较小的数与两者相除余数的最大公约数。
  Java代码实现：

/**
 * 欧几里德算法求最大公约数
 * @param m
 * @param n
 * @return
 */
private static int gcd(int m ,int n) {
    if (m <=0 || n <= 0) {
        throw new IllegalArgumentException("必须是正数");
    }
    if (n > m) {
        m ^= n;
        n ^= m;
        m ^= n;
    }
    int r;
    while ((r = m % n) != 0) {
        m = n;
        n = r;
    }
    return n;
}

  Python 代码如下：

def gcd(m, n):
    if m < n:
        m ^= n
        n ^= m
        m ^= n
    while m % n != 0:
        r = m % n
        m = n
        n = r
    return n