求2个数的最大公约数

• 求两个数的最大公约数，例如求371，196两个数的最大公约数

第1步：定义两个变量a,b，假如变量a保存的值为371，变量b保存的值为196，先求出两个数的余数并保存在变量r中

  a=371;

 b=196;

r = a%b;或者r=b%a；

   371 %  196 = 1   余  175

   或者 196 % 371 = 0 余   196

第二步:使用while循环判断余数r的值是否不为0

while(r != 0)

{

}

第三步:除数b的值变成被除数a的值，余数r的值变成除数b的值，重新计算余数r的值

a = b;

b = r;

r=a%b;

第四步：最后除数b的值就是两个数的最大公约数的值

整个计算方法，写成函数如下

int greatestCommonMeasure(int a,int b)
{
	int r = a % b;  // 求出两个数的余数
	while( r != 0)  // 余数是否为0
	{
		a = b;     // 除数变成被除数
		b = r;     // 余数变成除数
		r = a % b;  // 重新计算两数的余数
	}
	return b;    //返回两个数的最大公约数
}

为什么不需要判断最大数，其实不需要，这里巧妙地进行规避了，假如上例中，先求出196%371的余数，商为0，余

数为196，在while循环中，除数371变成被除数了，余数r变成除数，这样就纠正成最大数和最小数的求余，所以不需要

对两个数进行最大最小判断后来求余