今天下午在面試蘑菇街的時候章喉，面試官讓我寫如何求兩個數(shù)的最大公約數(shù)，思考了兩分鐘司蔬，想出了一個遞歸的想法；下來就寫了一下姨蝴，測試通過了俊啼，附上方法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);
        }
    }

后來又仔細看了看網(wǎng)上的教程，其實發(fā)現(xiàn)這是《編程之美》中的一個題似扔，有三種解法吨些，不過原型都是輾轉(zhuǎn)相除的思想。參考下面的博客炒辉，寫得挺好的豪墅。
http://blog.jobbole.com/106315/

附上Java代碼：

求出n與m%n的最大公約數(shù)

//下面方法中，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的最大公約數(shù)（解決兩個很大的數(shù)求模預算花銷很大的問題）

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均為偶數(shù)黔寇，最大公約數(shù)則為2*gcdEuclidean2(m / 2, n / 2);
如果一個為奇數(shù)偶器，則其中一個除以2；
兩個都為奇數(shù)缝裤，則直接按照第二種方法求得屏轰。
（解決如1000000 和 1這種情況，相減的次數(shù)就會特別多憋飞，通過右移的方式除以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);
                }
            }
        }
    }