求最大公约数的原理及算法实现
-
1.
辗转相除法
GCD
算法的基本原理
DCD - Greatest Common
Divisor
欧几里得定理：
若
a = b * r + q
，则
GCD(a,b) =
GCD(b,q)
。
证明：
假设
c =
GCD(a,b)
则
存在
m
使得
a = m * c,b = n * c;
因为
a = b * r + q,
则
q = a - b * r = m * c - n * c * r = (m
- n * r) * c;
因为
b
= n * c , q = (m - n * r) * c
故要证明
GCD(a,b) =
GCD(b,q)
，即证明
n
与
m - n *
r
互质
下面证明
m-
n×r
与
n
互质：
假设不互质，则存在公约数<
/p>
k
使得
m - n * r = x
* k, n = y * k.
则
:
a
= m * c = (n *
r + x * k) * c = (y * k * r + x * k) * c = (y * r
+
x) * k * c
b = n * c = y * c * k
则
GCD(a,b) = k *
c,
与
c=gcd(a, b)
矛盾
2.
辗转相除法算法的实现
2.1
递归实现
int
GCD
(
int
a
,
int
b
)
{
if
(!
b
)
return
a
;
else
return
GCD
(
b
,
a
%
b
);
}
自己改进
int
GCD
(
int
a
,
int
b
)
{
if
(!(
a
%
b
))
return
b
;
else
return
GCD
(
b
,
a
%
b
);
}
2.2
迭代实现
int
GCD
(
int
a
,
int
b
)
{
int
c
=
a
%
b
;
while
(
c
)
{
a
=
b
;
b
=
c
;
c
=
a
%
b
;
}
return
b
;
}
3.
更相减损法
更相减损术
，是出自《
九章算术
》
的一种求最大公约数的算法，它原本是为
约分
而设计
的，但它适用于任何需要求最大公约数的场合。
《九章算术》
是中国古代的数学专著，
其中的
“
更相减损术
”
可以用来求两个数的最大公
约数，即
“
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等
也。
以等数约之。
”
翻译成现代语言如下：
第一步：任意
给定两个正整数；判断它们是否都是偶数。若是，则用
2
约简；
若不是则
执行第二步。
第二步：以较
大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小
数。继续这个操
作，直到所得的减数和差相等为止。
则第一步中约掉的若干个
2
与第二步中等数的乘积就是所求的最大公约数。
其中所说的
“
等数
”
，就是最大公约数。求
“
< br>等数
”
的办法是
“
更相减损
”
法。所以更相减
损法也叫等值算法。
例如：用更相减损术求
260
和
< br>104
的最大公约数。
解：由
于
260
和
104
均为偶数，首先用
2
约简得到
13
0
和
52
，再用
2
约简得到
65
和
< br>26
。
此时
< br>65
是奇数而
26
不是奇数，故
把
65
和
26
辗转相减：
65-26=39
39-26=13
26-13=13
所以，
260
与
104
的最大公约数等于
13
乘以第一步中约掉的两个
2
，即
13*2*2=52
。
2.
更相减损法算法的实现
2.1
递归实现
#include
int
main
(
void
)
{
int
num
=
0
,
result
,
a
,
b
;
scanf
(
,&
a
,&
b
);
while
(
!(
a
%
2
)
&&
!(
b
%
2
))
{
num
++;
a
/=
2
;
b
/=
2
;
}
result
=
pow(2,num)
*
GCD
(
a
,
b
);
printf
(
,
result
);