如何求出两个数的最大公因数-创新互联

其实我们可以用一个非常好理解的方法来做——辗转相除法。什么是辗转相除法？它是一个循环的过程，我们设a为被除数，b为除数，每一次将当前的除数作为下一次循环的被除数，将a除以b的余数作为下一次循环的除数，这样一直循环下去，直到除数等于0才停止。这时，被除数就是大公因数。

举个例子

求24,9的大公因数：

24/9=2......6

这时我们以9为下一轮的被除数，6为下一轮的除数。

9/6=1......3

我们再以6为下一轮的被除数，3为下一轮的除数。

6/3=2......0

我们再以3为下一轮的被除数，0为下一轮的除数。

可是除数为0了，不能再循环下去了。这时，3就是24和9的大因数。

在这里我们有两种方法来实现。

第一种：递归实现。

#includeusing namespace std;
int f(int a,int b)
{
	if(b==0)return a;  //当除数b为0时，a就是大公因数
	return f(b,a%b); 
}
int main()
{
	int a,b;
	cin>>a>>b;    //a为被除数，b为除数 
	cout<

第二种：循环实现

#includeusing namespace std;
int main()
{
	int a,b;
	cin>>a>>b;    //a为被除数，b为除数
	while(b>0)
	{
		int t=a;  //保存被除数的值
		a=b;      //除数b变成被除数a
		b=t%b;    //注意，a的值已经变了，只能用t来除以b 
	}
	cout<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧