欧几里得算法求最大公约数

欧几里得算法求最大公约数

欧几里得算法又名辗转相除法，应该算是研究数论的基础算法
首先关于欧几里得算法的严谨的数学证明请看《几何原本》，作为程序员我们只要大致理解其数学思想就好，更重要的是其在赛场上的算法应用
其数学思想请看欧几里得算法的简单易懂的数学演绎
最大公约数gcd，最小公倍数lcm，lcm(a,b)=a*b/gcd(a,b)这是求最小公倍数的公式

#include<iostream>
using namespace std;
int gcd(int a,int b) //欧几里得算法，又名辗转相除法 
{   //求最大公约数
	int temp;
	while(b!=0)
	{
		temp=a%b;
		a=b;
		b=temp;
	}
	return a;
}
int main()
{
	int a,b,lcm;
	while(cin>>a>>b)
	{
		int GCD=gcd(a,b);
		cout<<GCD<<endl;
		lcm=a/GCD*b;  //最小公倍数，先除再乘，防止数值溢出！！！ 
		cout<<lcm<<endl;
	}
    return 0;	
} 

尤其要注意先除后乘！！！这可能就是题目的坑点。
下面介绍一些数学概念，为接下来一个月的数论学习开头
合数：大于1的非素数的正整数成为合数
a和b互素：即gcd(a,b)=1，则称a和b互素