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