求解最小公倍數(shù)和最大公約數(shù)是我們開(kāi)始編程的時(shí)候經(jīng)常需要練習(xí)的題目。從題面上看，好像我們需要求解的是兩個(gè)題目，但其實(shí)就是一個(gè)題目。那就是求最大公約數(shù)？為什么呢？我們可以假想這兩個(gè)數(shù)m和n，假設(shè)m和n的最大公約數(shù)是a。那么我們可以這樣寫(xiě)：

m = b a； n = c a;

所以m和n的最小公倍數(shù)就應(yīng)該是abc啊，那不就是m * n / a，其中m和n是已知的，而a就是那個(gè)需要求解的最大公約數(shù)。所以就有了下面的代碼，

int GetMinCommonMultiple(int m, int n)  
{  
    assert(m && n);  

    return m * n / GetMaxCommonDivide(m, n);  
} 

下面就可以開(kāi)始最大公約數(shù)的求解。其實(shí)，關(guān)于最大公約數(shù)的求解，大家看到的更多是各種捷徑，比如說(shuō)歐幾里得法。歐幾里得法構(gòu)思十分巧妙，它利用了m、n和n、m%n之間的最大公約數(shù)是相等的這一重要條件，充分利用替換的方法，在 m%n等于0的那一剎那，獲得我們的最大公約數(shù)。然而，我們平時(shí)自己所能想到的方法卻不多，下面的方法就是具有典型意義的一種：

• 首先對(duì)數(shù)據(jù)m和n判斷大小，小的賦值給smaller，大的賦值給larger

• index索引從2開(kāi)始到smaller遍歷，發(fā)現(xiàn)有沒(méi)有數(shù)據(jù)可以同時(shí)被兩者整除，有則更新數(shù)據(jù)

• 循環(huán)結(jié)束后，獲取最大的公約數(shù)

int GetMaxCommonDivide(int n, int m)  
{  
    int index;  
    int smaller;  
    int larger;  
    int value;  
    assert(n && m);  

    if(n > m){  
        larger = n;  
        smaller = m;  
    }else{  
        larger = m;  
        smaller = n;  
    }  

    value = 1;  
    for(index = 2; index <= smaller; index++){  
        if(0 == (smaller % index) && 0 == (larger % index))  
            value = index;  
    }  

    return value;  
}  

上面的代碼看似沒(méi)有問(wèn)題，但是還是留下了一個(gè)遺憾，如果m和n的數(shù)據(jù)都大于32位，那怎么辦？也許有的朋友會(huì)說(shuō)，現(xiàn)在有64位的cpu。但是如果我們此刻沒(méi)有64位的cpu，那該怎么辦呢？

總結(jié)：

• 看似最大公約數(shù)、最小公倍數(shù)是個(gè)小問(wèn)題，但是要寫(xiě)好不容易，算法、參數(shù)判斷、邏輯都要注意，
• 如果m和n的數(shù)據(jù)都比較大，有沒(méi)有可能利用多核降低計(jì)算的復(fù)雜度，
• 如果m和n中有數(shù)據(jù)大于32位，那該怎么辦？
• 小問(wèn)題看似簡(jiǎn)單，但是在不同的場(chǎng)景下卻可以變得非常復(fù)雜，作為面試題可以充分考察面試者的溝通能力和應(yīng)變能力。