歐幾里德算法
歐幾里德算法(輾轉(zhuǎn)相除法)，用于計算兩個整數(shù)a,b的最大公約數(shù)。
其計算原理依賴于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設(shè)d是a,b的一個公約數(shù)，則有 d|a, d|b，
而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數(shù)
假設(shè)d 是(b,a mod b)的公約數(shù)，則
d | b , d |r ，但是a = kb + r
因此d也是(a,b)的公約數(shù)
因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證!
（注 x|y：y可以被x整除，即 y mod x == 0 ）
算法描述：
前提：a?
>
?b?
>
?
0
?.
返回：a,b的最大公約數(shù)。
程序：
int
?gcd(
int
?a,?
int
?b)
{
????
for
(
int
?r?
=
?a?
%
?b;?r?
!=
?
0
;?r?
=
?a?
%
?b){
????????a?
=
?b;
????????b?
=
?r;????????
????}
????
return
?b;
}
本知識來源于網(wǎng)絡(luò).