算法设计，源码，复杂度最小的三种求最大公约数的方法，源码

#include <iostream.h> long gcd1(long x,long y) {//直接实现辗转相除法 对于大整数而言，取模运算开销非常昂贵 return (!y)?x:gcd1(y,x%y); } long gcd2(long x,long y) {//免去了大整数除法 但是迭代次数比以前的迭代次数多了很多 if (x<y) { return gcd2(y,x); } if (y==0) { return x; } else { return gcd2(x-y,y); } } long gcd3(long x,long y) {//最优的算法 if (x<y) { return gcd3(y,x); } if (y==0) { return x; } else { if (x%2==0) {//x is even if (y%2==0) {//y is even return (gcd3(x>>1,y>>1)<<1); } else { return gcd3(x>>1,y); } } else { if (y%2==0) {//y is even return gcd3(x,y>>1); } else { return gcd3(y,x-y); } } } } void main() { // cout<<gcd1(100000,1)<<endl; // cout<<gcd2(100000,1)<<endl; cout<<gcd3(100000,1)<<endl; }