定义
辗转相除法,被称为欧几里得(Euclidean)算法,是求最大公约数的算法。
基本原理
原理
两个正整数a和b(a > b),他们的最大公约数等于a除以b的余数和b之间的最大公约数。
证明
设 b = aq + r, (a,b) 为a, b的最大公约数
则a % (a,b) = 0; b % (a,b) = 0,
因为(a和b的约束) % (a,b) = 0,
所以 (b - aq) % (a,b) = 0
即 r % (a,b) = 0
因为a % (a,b) = 0, r % (a,b) = 0
所以(a,r) % (a,b) = 0(最大公约数一定被公约数整除)
又因为a % (a,r) = 0, r % (a,r) = 0, b = aq+r
所以 (aq + r) % (a,r) = 0
即 b % (a,r) = 0
因为 a % (a,r) = 0
b % (a,r) = 0
所以
(a,b) % (a,r) = 0
所以
(a,b) = (a,r)
算法实现
思想
a = b * q1 + r1
b = r1 * q2 + r2
r1 = r2*q3 + r3
…
rn-2 = rn-1 * qn + rn
rn-1 = 0, rn-2 即为最大公约数(
因为rn-2和0的最大公约数就是他本身rn-2,
又因为rn-2和0的最大公约数等于a和b的最大公约数,
所以rn-2即为a和b的最大公约数。
C语言实现
#include <stdio.h>
int main()
{
int a;
int b;
scanf("%d %d", &a, &b);
int u, v;
u = a, v = b;
while (v != 0)
{
int tmp1 = u % v;
u = v;
v = tmp1;
}
printf("%d\n", u);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)