C++算法之求最大公約數和最小公倍數

求解最小公倍數和最大公約數是我們開始編程的時候經常需要練習的題目。從題面上看，好像我們需要求解的是兩個題目，但其實就是一個題目。那就是求最大公約數？為什么呢？我們可以假想這兩個數m和n，假設m和n的最大公約數是a。
那么我們可以這樣寫：
    m = b a；
    n = c  a;
    所以m和n的最小公倍數就應該是abc啊，那不就是m * n / a，其中m和n是已知的，而a就是那個需要求解的最大公約數。所以就有了下面的代碼，

int GetMinCommonMultiple(int m, int n)

{

    assert(m && n);


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

}

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

     a） 首先對數據m和n判斷大小，小的賦值給smaller，大的賦值給larger 

     b）index索引從2開始到smaller遍歷，發現有沒有數據可以同時被兩者整除，有則更新數據 

     c）循環結束后，獲取最大的公約數
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;  

}
</pre>     上面的代碼看似沒有問題，但是還是留下了一個遺憾，如果m和n的數據都大于32位，那怎么辦？也許有的朋友會說，現在有64位的cpu。但是如果我們此刻沒有64位的cpu，那該怎么辦呢？ 

 

 總結： 

     （1）看似最大公約數、最小公倍數是個小問題，但是要寫好不容易，算法、參數判斷、邏輯都要注意， 

     （2）如果m和n的數據都比較大，有沒有可能利用多核降低計算的復雜度， 

     （3）如果m和n中有數據大于32位，那該怎么辦？ 

     （4）小問題看似簡單，但是在不同的場景下卻可以變得非常復雜，作為面試題可以充分考察面試者的溝通能力和應變能力。