辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数、最小公倍数就是这两个数的乘积除以最大公约数。

设两数为a、b(a≥b),求a和b最大公约数(a,b)的步骤如下:

(1)、用a除以b,得 a÷b=q…r1。

(2)、若r1=0,则 (a,b)=b;

(3)、若r1≠0,则再用b除以r1,得 b÷r1=q…r2 .

(4)、若r2=0,则 (a,b)=r1;若 r2≠0 ,则继续用r1除以r2,……,如此下去,直到能整除为止。

其最后一个余数为0的除数即为(a,b)的最大公约数。

示例代码(递归)

int getGCD(int a, int b)
{
    if (a % b == 0)
	{
    	return b;
    }    
    return getGCD(b, a % b);
}