最小公倍数

定义

最小公倍数（Least Common Multiple，缩写L.C.M.），对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。(--转自百度百科最小公倍数)

算法

常规算法

lcm(a,b)=a*b/gcd(a,b)

直接算法

由于gcd(a,b)=gcd(a,b mod a)

所以lcm(a,b)=a*b/gcd(a,b)=a*b/gcd(b mod a,a)=lcm(b mod a,a)*b/(b mod a)，特别地，当b是a的倍数的时候最小公倍数显然是b。然后递归求解。

此时也可以用a*b/lcm(a,b)求最大公约数。

这种算法的优势是不会出现可能被屏蔽的gcd字样，以及相关的内容，又不会让人难以理解。

缺点是系数比较大，速度会略微的慢一点。

算法实现

Function Euclid(a,b:longint):longint;
 
begin
   if b=0 then exit(a)
   else exit(Euclid(b,a mod b));
end;
 
begin
  readln(a,b);
  c:=Euclid(a,b);
  writeln(a*b div c);
end.