C++求两个数的最大公约数

思路一：给定a，b两个数，将较小的数赋值给c，令c=b（不妨设a>b），将a和b对c做求余运算，从c开始依次减1向下遍历，直到两者的余数都为0则返回c，否则继续循环遍历。代码如下：#include<iostream.h>int gcd(int a,int b){int c;c=(a>b)?b:a;while(a%c!=0||b%c!=0){c...

spirits_of_snail

35502人浏览 · 2017-04-13 20:25:19

spirits_of_snail · 2017-04-13 20:25:19 发布

思路一：给定a，b两个数，将较小的数赋值给c，令c=b（不妨设a>b），将a和b对c做求余运算，从c开始依次减1向下遍历，直到两者的余数都为0则返回c，否则继续循环遍历。

代码如下：

#include<iostream.h>

int gcd(int a,int b)
{	int c;
	c=(a>b)?b:a;
	while(a%c!=0||b%c!=0)
	{	c--;
	}
	return c;
}
int main()
{	int a,b,max_div;
	cout<<"please input two integer:";
	cin>>a>>b;
	max_div=gcd(a,b);
	cout<<"the greatest common divisor of ";
	cout<<a<<" and "<<b<<" is "<<max_div<<endl;
	return 0;
}

思路二：辗转相除法

假设a>b,如果a不能被b整除，则将b赋值给a，余数赋值给b，重复执行a%b,直到a能够被b整除。此时返回b的值，则为最大公约数。

代码如下：

#include<iostream.h>


int gcd2(int a,int b)
{	int c;
	if(a<b)
	{	a=a+b;
		b=a-b;
		a=a-b;
	}
	c=a%b;
	while(a%b!=0)
	{	a=b;
		b=c;
		c=a%b;	
	}
	return b;
}

int main()
{	int a,b,max_div;
	cout<<"please input two integer:";
	cin>>a>>b;
	max_div=gcd2(a,b);
	cout<<"the greatest common divisor of ";
	cout<<a<<" and "<<b<<" is "<<max_div<<endl;
	return 0;
}

很显然：方法2比方法1更加高效，优先推荐使用方法2

参考文献：http://blog.csdn.net/a1414345/article/details/51770430