最大公因数最小公倍数 C语言函数

叶茂林

发布于 2023-07-28 20:00:52

2310

发布于 2023-07-28 20:00:52

文章被收录于专栏：叶子的开发者社区

碎碎念念

最大公因数的话，用欧几里得的辗转相除法。。

最小公倍数的话，最直接就是一个从2到这两数乘积的循环，看哪个数同时被这两数整除。

实际上，根据数学原理，两个数的最小公倍数等于两个数的乘积除以两个数的最大公因数。

代码

#include<stdio.h>
int max(int a,int b)
{
	int r;
	while(b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;	
}
int min(int a,int b)
{
	return a*b/max(a,b);
}
int main()
{
	int t,x,y;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&x,&y);
		printf("%d %d\n",max(x,y),min(x,y));
	} 
	return 0;
}