辗转相除法求最两数最大公约数

辗转相除法的理论基础：欧几里德算法。

定理：gcd(a,b) = gcd(b,a mod b)  前提：a > b 

证明：

a可以表示成 a = kb + r，则r = a % b 
假设d是a,b的一个公约数，则有 
a  % d =0, b % d = 0，而r = a - kb，因此 r % d  = (a - kb)  % d  = 0
因此d是(b, a % b)的公约数,

即a 和 b的公约数也是a对b求模的结果的公约数 

假设d 是(b,a % b)的公约数，则 
b % d  = 0, r % d = 0，但是a = kb +r 
因此 a % d  = (kb +r ) % d = 0 

因此d也是(a,b)的公约数 

下面是用辗转相除法求最大公约数的递归和非递归方法：

#include

//辗转相除求最大公约数 递归方法

int fun(int x,int y)

{

int r = 0;

if(x < y) fun(y,x);

else if(y == 0) return x;

else

{

r = x % y;

return fun(y,r);

}

}

//辗转相除求最大公约数，非递归方法

int fun1(int x,int y)

{

int r;

if (x < y)

{

x = x + y;

y = x - y;

x = x - y;

}

do

{

r = x % y;

x = y;

y = r;

}while (r != 0);

return x;

}