辗转相处求最大公约数

无言面对”江东父老“了，接触编程一年了，今天发现还不会辗转相除法求最大公约数。惭愧惭愧！

 

为此，总结一下以方便日后忘了好查找。

 

1.输入要比较的两个数a,b

 

忽略：2.比较大小（因为后面要的是大的数对小的数做%操作）

 

3.辗转相除（用循环不停的取余，如a%b,直至b=0）

 

4.最后的a为两数的最大公约数

 

于是代码如下：

//求最大公约数的函数
int maxGY(int a,int b)
{
	//判断大小（可以不判断）
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (b!=0)
	{
		//大的对小的取余
		int m = a%b;
		a = b;
		b = m;
	}
	//返回最大公约数
	return a;
}

 

有了最大公约数，最小公倍数也就easy了，

最小公倍数=数1*数2/最大公约数。

代码如下：

 

//求最小公倍数的函数
int minGB(int a,int b)
{
	//先求最大公约数
	int m = maxGY(a, b);
	int n = a*b / m;
	return n;
}

 

 

 

评论

2 楼 沐刃青蛟 2015-07-09  

好吧

1 楼 kyzaqlx 2015-06-29  

为什么一定要比较两个数的大小先呢？不需要的~~~