C语言——练习：求最大公约数（GCD）和最小公倍数(LCM)

1.输入两个数得到其最大公约数和最小公倍数

（1）分析

在C语言中，求两个数的最大公约数（Greatest Common Divisor, GCD）和最大公倍数（Least Common Multiple, LCM）是常见的编程练习。首先，我们需要明确如何求两个数的最大公约数，然后再利用这个最大公约数来求得最大公倍数。

最大公约数（GCD）:

最大公约数可以使用多种算法来求解，但欧几里得算法（Euclidean algorithm）是最著名且最常用的一种。该算法的基本思想是：gcd(a, b) = gcd(b, a mod b)，其中a和b是两个正整数，gcd代表最大公约数，mod代表取余运算。算法一直递归进行，直到b为0，此时a即为两数的最大公约数。

简单来说，计算的流程为：首先a%b，余数为c，如果c != 0，则a = b，b = c，继续循环操作，直至a%b，余数为0，此时的b即为最大公约数。

其中：余数为0有两种情况：

1.a<b  ：执行上述操作会将a和b的值进行交换，继续循环直至a可以被b整除，余数为0。

2.a可以被b整除：此时b的值就是最大公约数。

最大公倍数（LCM）:

在得到两个数的最大公约数之后，我们可以利用以下公式来求得它们的最大公倍数：

LCM(a,b)=∣a×b∣​/GCD(a,b)

即最小公倍数=a和b的乘积除以最大公约数。

这里使用绝对值是因为a和b可能为负数，但最大公倍数定义为正数。

（2）代码实现

#include<stdio.h>

int getGcd(int a,int b)   //求最大公约数函数
{
	while(a%b != 0){        //只要余数不为0，进入循环
	                       //余数为0有两种情况：1.a<b  2.a可以被b整除
		int temp = b;     //先保留b原始的值
		b = a%b;         //将余数赋给b
		a = temp;       //将原始的b值赋给a
		printf("a=%d,b=%d\n",a,b);  //测试语句，打印出每次循环a和b的值
	}
	
	return b;
}

int getLcm(int a,int b,int dataGcd)  //求最小公倍数函数
{
	int dataLcm;
	
	dataLcm = a*b/dataGcd;
	
	return dataLcm;
}

int main()
{
	int data1;
	int data2;
	int dataGcd;
	int dataLcm;
	
	printf("请输入两个整数：\n");
	scanf("%d%d",&data1,&data2);
	
	dataGcd = getGcd(data1,data2);
	dataLcm = getLcm(data1,data2,dataGcd);
	
	printf("%d和%d的最大公约数为：%d，最小公倍数为：%d",data1,data2,dataGcd,dataLcm);
	return 0;
}

输出将是：

请输入两个整数：
2
11
a=11,b=2
a=2,b=1
2和11的最大公约数为：1，最小公倍数为：22