/* 最大公约数 */ #include <stdio.h> /* 方法1:辗转相除 缺点:对于大整数,取模运算开销大 */ int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } /* 方法2: 缺点:迭代次数过多 */ int gcd2(int x,int y){ if(x<y) return gcd2(y,x); return y==0?x:gcd2(x-y,y); } /* 方法3: 1、如果y=k*y1,x=k*x1,那么有f(y,x)=k*f(y1,x1) 2、如果x=p*x1,且y%p!=0,假设p为素数,那么有f(x,y)=f(p*x1,y)=f(x1,y) 取p=2 若x,y为偶数,f(x,y)=2*f(x>>1,y>>1) 若x为偶数,y为奇数,f(x,y)=f(x>>1,y) 若x为奇数,y为偶数,f(x,y)=f(x,y>>1) 若x,y均为奇数,f(x,y)=f(x,x-y) */ int gcd3(int x,int y){ if(x<y) return gcd(y,x); if(y==0) return x; else{ if(!(x&1)){ if(!(y&1)) return gcd3(x>>1,y>>1)<<1; return gcd3(x>>1,y); } else{ if(!(y&1)) return gcd3(x,y>>1); return gcd(y,x-y); } } } int main(){ int a=12,b=8; printf("%d\n%d\n%d\n",gcd(a,b),gcd2(a,b),gcd3(a,b)); return 0; }
原文:http://blog.csdn.net/starcuan/article/details/21252757