C++ 最小公倍数和最大公约数

参考博客连接
两者之间的关系
x和y的最小公倍数和最大公约数的关系

X*Y = 最小公倍数 * 最大公约数

1.辗转相除法

int test(int x,int y){
	while(x%y!=0){
		int z=x;
		x=y;
		y=z%y;
	}
	return y;
}

2.暴力

int test1(int x,int y){
	int ans=1;
	for(int i=1;i<=x;i++)
		if(y%i==0 && x%i==0)
			ans=i;
	return ans;
}

3.递归

int test2(int x,int y){
	if(x%y==0)
		return y;
	else
		return test2(y,x%y);
}

利用最小公倍数和最大公约数之间的关系即可求出
最小公倍数 = x*y/最大公约数