最大公约数和最小公倍数
[cpp]
//辗转相除法求最大公约数
int GCD(int m,int n)
{
int tem;
if(m while(n!=0){
tem=m%n;
m=n;
n=tem;
}
return m;
}
//辗转相减法求最大公约数
int GCD(int m,int n)
{
int tem;
while(n!=0){
if(m tem=m-n;
m=n;
n=tem;
}
return m;
}
//最小共倍数等于m*n/最大公约数,所以求出了最大公约数就能很快得出最小公倍数啦
int LCM(int m,int n)
{
return m*n/GCD(m,n);
}
摘自 菜鸟的高手情节
|