辗转相除法求最两数最大公约数
时间：2010-07-31 来源：chinawanglun
辗转相除法的理论基础：欧几里德算法。
定理：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 <stdio.h>
//辗转相除求最大公约数 递归方法
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; }
证明： 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 <stdio.h>
//辗转相除求最大公约数 递归方法
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; }
相关阅读 更多 +
