两个数的最大公约数

今天下午在面试蘑菇街的时候，面试官让我写如何求两个数的最大公约数，思考了两分钟，想出了一个递归的想法；下来就写了一下，测试通过了，附上方法Java代码：

 //m比n小
public static int gcdloop(int m, int n) {     
        if (m < 2) {
            return 1;
        }
        boolean flag = false;
        int result = 1;
        for (int i = 2; i <= m; i++) {
            if ((m % i == 0) && (n % i == 0)) {
                flag = true;
                result = i;
                break;
            }
        }
        if (!flag) {
            return result;
        }
        else {
            return result * gcdloop(m/result, n/result);
        }
    }

后来又仔细看了看网上的教程，其实发现这是《编程之美》中的一个题，有三种解法，不过原型都是辗转相除的思想。参考下面的博客，写得挺好的。
http://blog.jobbole.com/106315/

附上Java代码：

求出n与m%n的最大公约数

//下面方法中，m均大于n
public static int gcdEuclidean(int m, int n) {
        if (n%m == 0) {
            return m;
        }
        else {
            return gcdEuclidean(n, m%n);
        }
    }

求出n与m-n的最大公约数（解决两个很大的数求模预算花销很大的问题）

public static int gcdEuclidean1(int m, int n) {
        if (m < n) {
            return gcdEuclidean1(n, m);
        }
        if (n == 0) {
            return m;
        }
        else {
            return gcdEuclidean1(m - n, n);
        }
    }

当m与n均为偶数，最大公约数则为2*gcdEuclidean2(m / 2, n / 2);
如果一个为奇数，则其中一个除以2；
两个都为奇数，则直接按照第二种方法求得。
（解决如1000000 和 1这种情况，相减的次数就会特别多，通过右移的方式除以2）

public static int gcdEuclidean2(int m, int n) {
        if (m < n) {
            return gcdEuclidean2(n, m);
        }
        if (n == 0) {
            return m;
        }
        else {
            if (m % 2 == 0) {
                if (n % 2 == 0) {
                    return (gcdEuclidean2(m >> 1, n >> 1) << 1);
                }
                else {
                    return gcdEuclidean2(m >> 1, n);
                }
            }
            else {
                if (n % 2 == 0) {
                    return gcdEuclidean2(m, n >> 1);
                }
                else {
                    return gcdEuclidean2(n, m - n);
                }
            }
        }
    }