最大公約數，最小公倍數

求兩個數的最大公約數，輾轉相除法無疑是一個很棒的算法，接下來就說說輾轉相除法并代碼實作它吧！ps：萌新第一次寫，不好的地方就這樣看着吧，反正你又不能順着網線來揍我。

輾轉相除法過程和證明過程可以百度一下啦，下面直接給出代碼實作吧

#include<stdlib.h>
#include<stdio.h>
/*
輸入兩個整數，求它們的最大公約數和最小公倍數


*/
int main (void){
	int gcd(int x,int y);//最大公約數
	int lcm(int x,int y);//最小公倍數
	printf("輸入兩個整數：");
	int a,b;
	scanf("%d  %d",&a,&b);	
	printf("%d和%d的最大公約數為%d\n",a,b,gcd(a,b));
	printf("%d和%d的最小公倍數為%d\n",a,b,lcm(a,b));

	return 0;
}

int gcd(int x,int y){//最大公約數
	if(y>x){//保證x>y
		int temp=x;
		x=y;
		y=temp;
	}
	int m=x%y;//餘數
	while(m!=0){//餘數為0結束
		x=y;
		y=m;
		m=x%y;
	}
	return y;//最大公約數
}

int lcm(int x,int y){//最小公倍數
	int m=gcd(x,y);//調用最大公約數

	return m*(x/m)*(y/m);//生成最小公倍數

}