求两个数的最大公约数【ACM基础题】

/*
* 求两个数的最大公约数
* xtfggef 2012/5/16
*/
#include<stdio.h>

int gcd(int,int);
void main()
{
	int a = 5;
	int b = 8;
	int c = gcd(a,b);
	printf("%d\n",c);
}
int gcd(int a, int b)
{
	while(a!=b)
	{
		if(a>b)
			a=a-b;
		else
			b=b-a;
	}
	return a;
}

最小公倍数类似，借助于最小公倍数=X*Y/gcd(X,Y);就OK了。

此处注意：为了使计算不超出范围，最好写成：X/gcd(X,Y)*Y