一、原理
假设两个数 a=36 b=27
辗转相除法: 大数÷小数;小数÷余数 ;直到余数为0。
36÷27=1……9 (商1 余9)
27÷9=3……0
则最大公约数为 9
则最小公倍数为 a*b/remainder(公约数)
总结:最大公约数*最小公倍数=max*min
二、上码:
int main()
{
int a = 36;
int b = 27;
int max = a > b ? a : b;
int min = a < b ? a : b;
int common_multiple = 0; //公倍数
int common_divisor = 0; //公约数
int remainder = 1; //余数
while (remainder) //由此可见,reminder不能初始化为0
{
remainder = max % min;
if (remainder != 0)
{
max = min;
min = remainder;
}
}
common_divisor = min; //公约数
common_multiple = a * b / common_divisor; //公倍数
printf("%d %d", common_divisor, common_multiple);
return 0;
}