编程之美-最大公约数问题

求最大公约数早在300年前左右，欧几里得就在他的著作《几何原本》中给出了高效的解法--辗转相除法，但是当整数非常大的时候，对大整数而言，取模运算和除法运算是非常昂贵的开销，这将成为整个算法的瓶颈。

code：

#include
using namespace std;
//传统意义的求最大公约数
/*这里约定x比y大
原理是：
k=x/y
b=x%y
x=k*y+b；
如果一个数能同时整除x,y，则必能同时整数b，y则
f(x,y)=f(y,x%y);
f(x,y)=f(x%y,y);
*/
int GCD_tra(int a,int b){
      //9,36
      if(a==0) return b;
      if(a       return (!a)?b:GCD_tra(a%b,b); 
}
//这种算法适合于x,y相差不大的情况，如果x，y差值很大，不建议选取该种算法
/**
一个数如果能同时整数x和y，则必能同时整除x-y和y
即f(x,y)=f(y,x-y);
f(x,y)=f(x-y,y);
*/
int GCD_mod(int x,int y){
    if(x             return GCD_mod(y,x);
    }
    if(y==0) return x;
    else return GCD_mod(x-y,y);
}
int main(){
    int a,b;
    cout<<"请输入两个数a b:";
    cin>>a>>b;
    int c=GCD_tra(a,b);
    cout<     system("pause");
    return 0;   
}