求最大公约数

梦想游戏人
目录:
algorithm

原理是利用了辗转相除

  • int gcd(int x,int y)
  • {
  • int temp=0;
  • while(y)
  • {
  • temp=y;
  • y=x%y;
  • x=temp;
  • }
  • return x;
  • }
  • 最小公倍数=x*y/gcd(x,y)
int gcd(int x,int y)
{
	int temp=0;
	while(y)
	{
	    temp=y;
	    y=x%y;
	    x=temp;
	}
	return x;
}

最小公倍数=x*y/gcd(x,y)
Scroll Up