各种求最大公约数的函数

GCD 求最大公约数函数

方法总结

• 递归版

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

• 简洁递归版

int gcd(int x, int y)
{
	return y>0? gcd(y, x%y) : x;
}

• 非递归版

int gcd(int x, int y)
{
	int tmp;
	while(y>0)
	{
		tmp=x%y;
		x=y;
		y=tmp;
	}
	return x;
}

• (algorithm.h)头文件中的函数

__gcd(x, y) //注意是两个下划线，这个可以直接调用，返回x和y的最大公约数
    //但是有些oj上不支持这个，还有说这个函数不是标准函数，需要注意。