給定兩個(gè)正整數(shù)，求其最大公約數(shù)，相信這是每一個(gè)寫代碼的同學(xué)絕壁遇見過的練習(xí)，當(dāng)然解法也非常多，下面先給出一個(gè)沒有經(jīng)過任何算法處理的程序：

public static int getResult(int a,int b){  
int max = (a>b)?a:b;  
    int result=0;  
    for(int i = 1;i < max;i++){  
        if(a%i == 0 && b%i == 0){  
            result=i;  
        }  
    }  
    return result;  
}  

這樣當(dāng)然是可以解出來的，但是要循環(huán)遍歷其中較大的正整數(shù)，如果兩個(gè)數(shù)量都非常大的話，效率是非常低的，每當(dāng)遇到效率低下的程序，我們必然會(huì)想到優(yōu)化，算法優(yōu)化總是很靠譜的一種方法。下面就列出幾種添加算法的方法來解決最大公約數(shù)的問題。

解法一：

輾轉(zhuǎn)相除法，假設(shè)求正整數(shù) num1,num2 的最大公約數(shù)，假設(shè)f(x,y)為兩者的最大公約數(shù),取 k = x / y (取整)，b = x % y (取余)；則 x = k y + b ;那么能同時(shí)被x ，y整除的數(shù)必然也同時(shí)能被 b , y 整除，能被b ， y整除的數(shù)也能同時(shí)被x，y整除，也就是說，x，y的最大公約數(shù)就是b，y的最大公約數(shù)，則有 f (x , y) = f(y , x%y) (x>=y>0),這樣遞歸運(yùn)算，比如

f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; 這樣將運(yùn)算次數(shù)直接降低了很多。下面附上代碼：

int result = ((y == 0) ? x : gcd(y, x % y));  
    return result;  
} 

解法二：

解法一雖然很好的解決了求公約數(shù)的問題，但是算法中包含有除法，在計(jì)算機(jī)中除法的開銷是很大的，能不能不用除法呢?？梢赃@樣考慮，一個(gè)數(shù)能被x , y整出，必然也能被x-y，y整出，也就是一個(gè)數(shù)被x，y整出是這個(gè)數(shù)被x-y，y整出的充分必要條件。那么f(x, y) = f(x-y , y);這樣計(jì)算的話，就可以把大整數(shù)之間的取模運(yùn)算轉(zhuǎn)換為大整數(shù)之間的減法運(yùn)算。由于f（x，y）= f（y，x），為了避免求出一個(gè)正數(shù)和一個(gè)負(fù)數(shù)的最大公約數(shù)，要靈活運(yùn)用f（x，y）= f（y，x）,迭代進(jìn)行，直到一方為0；比如：

f(42,30) = f(30,12) = f(18 , 12)= f(12 , 6) = f(6,6)= f(6 , 0) = 6;這樣運(yùn)算跟上面的方法比起來，優(yōu)化了大數(shù)據(jù)取模的問題，但是運(yùn)算次數(shù)會(huì)增大，代碼如下：

private static int gcd(int x, int y) {

if (y == 0) {  
        return x;  
    }  
    if (x < y) {  
        return gcd(y, x);  
    } else {  
        return gcd(x - y, y);  
    }  
} 

解法三：

解法一的不足之處在于復(fù)雜的大數(shù)據(jù)除法運(yùn)算，解法二雖然干掉了大數(shù)據(jù)的除法運(yùn)算，但是增加了操作次數(shù)。兩種方法都不是非常的完美，那么我們就用第三種方法來解決，第三種方法使用的二進(jìn)制方案，估計(jì)很多同學(xué)看到01100100就要放棄了，千萬不要，其實(shí)這東西不難。

對(duì)于x，y來說，有x=k * x1,y = k * y1 ,則f(x ,y) = f(k * x1,k * y1) = k * f(x1 ,y1);此為一。

另外，如果 x = p * x1,且p為素?cái)?shù)，y%p != 0,則f（x ，y）= f(p * x1, y) = f(x1 ,y);此為二。

由一和二兩個(gè)公式，我們可以計(jì)算公約數(shù)了：

設(shè)p=2：

假設(shè)x，y都是偶數(shù)：f（x，y）= 2f(x»1,y»1);

假設(shè)x是偶數(shù)，y是奇數(shù)：f(x,y) = f(x»1,y);

假設(shè)x是奇數(shù)，y是偶數(shù)：f(x,y) = f(x,y»1);

假設(shè)x，y都是奇數(shù)：f(x,y) = f(y,x-y);—這是根據(jù)解法二中推出來的

下面還以42 和 30 為例：

f(42,30) = f(101010,11110) = 2f(10101,1111) = 2f(1111,110)=2 * f(1111,11) = 2 f (1100,11) = 2f(110,11)=2 f(11,11) = 2 f(0,11) = 2 3=6

括號(hào)中均為二進(jìn)制表達(dá)，這樣最壞的情況下，復(fù)雜度也就是log 2(max(x,y));—-2是底數(shù)，尼瑪，這格式弄不出來。

下面附上代碼：

if (x < y) {  
        return gcd(y, x);  
    }  
    if (y == 0) {  
        return x;  
    }  
    if (isEven(x)) {  
        if (isEven(y)) {  
            // x，y都為偶數(shù)，f(x,y)=2*f(x/2,y/2)  
            return gcd(x >> 1, y >> 1) << 1;  
        } else {  
            // x偶數(shù),y奇數(shù)，f(x,y)=f(x/2,y)  
            return gcd(x >> 1, y);  
        }  
    } else {  
        if (isEven(y)) {  
            // x奇數(shù)，y偶數(shù)，f(x,y)=2*f(x,y/2)  
            return gcd(x, y >> 1);  
        } else {  
            // x，y都為奇數(shù)，f(x,y)=f(x-y,y)  
            return gcd(x - y, y);  
        }  
    }  
}  
 
public static boolean isEven(int x) {  
    return (x % 2 == 0) ? true : false;  
} 

以前根本沒有想過這么些玩意，第一次看算法，頓時(shí)感覺高大上啊，不過的確，看到這樣解決以前常用來解決的公約數(shù)問題，的確眼前一亮啊，希望大家多多給意見哦~

原文鏈接：http://my.oschina.net/u/858241/blog/209774