欧几里德算法 　　欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数.其计算原理依赖于下面的定理： 　　定理：gcd(a,b)=gcd(b,amodb) 　　证明：a可以表示成a=kb+r,则r=amodb 　　假设d是a,b的一个公约数,则有 　　d|a,d|b,而r=a-kb,因此d|r 　　因此d是(b,amodb)的公约数 　　假设d是(b,amodb)的公约数,则 　　d|b,d|r,但是a=kb+r 　　因此d也是(a,b)的公约数 　　因此(a,b)和(b,amodb)的公约数是一样的,其最大公约数也必然相等,得证. 　　欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为： 　　voidswap(int&a,int&b) 　　{ 　　intc=a; 　　a=b; 　　b=c; 　　} 　　intgcd(inta,intb) 　　{ 　　if(0==a) 　　{ 　　returnb; 　　} 　　if(0==b) 　　{ 　　returna; 　　} 　　if(a>b) 　　{ 　　swap(a,b); 　　} 　　intc; 　　for(c=a%b;c>0;c=a%b) 　　{ 　　a=b; 　　b=c; 　　} 　　returnb; 　　} 　　参考资料：internet