欧几里德算法

　　欧几里德算法又称辗转相除法,用于计算两个整数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