求2个数的最大公约数

2023-12-28 12:24| 来源: 网络整理| 查看: 265

求两个数的最大公约数，例如求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变成除数，这样就纠正成最大数和最小数的求余，所以不需要

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

【本文地址】

公司简介

联系我们