GESP等级考试C++5级17-辗转相除法

辗转相除法也叫欧几里得算法（Euclidean Algorithm），用于求两个正整数的最大公约数，最大公约数，也叫gcd, 是其英文名greatest common divisor的简写。

1.辗转相除法求最大公约数的原理

对于两个整数a和b，假设其最大公约数是d。那么a能被d整除，b也能被d整除，那么a mod b也能被d整除。也就是说，a和b的最大公约数与b和a mod b的最大公约数相同。如下公式所示。

gcd(a, b)=gcd(b, a mod b)

可以反复套用以上公式，直到a mod b为0为止，如下图公式所示。

gcd(a, 0) = a

此时a的值即为a和b的最大公约数。

例如，求48和18的最大公约数，如下所示。

gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0)