`
沐刃青蛟
  • 浏览: 6873 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

辗转相处求最大公约数

阅读更多

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

 

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

 

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  
为什么一定要比较两个数的大小先呢?不需要的~~~

相关推荐

Global site tag (gtag.js) - Google Analytics