LCM與GCD

求GCD常用輾轉相除法（歐幾裡得算法）

①例如求gcd(12, 18)： 先用12 % 18 == 12；

②再用上一輪模數（18）模上上一輪取模的結果（12）：18 % 12== 6；

③再用上一輪的模數（12）模上上一輪取模的結果（6）：12 % 6 == 0；

④發現結果等于0了，這時候的模數（6）就是最後的答案。

以下是gcd代碼：

int gcd(int a,int b)
{
  if(b == 0)
  return a;
  else
  return gcd(b,a%b);
}      

algorithm庫中有可以直接求gcd的函數__gcd();

求LCM

int lcm(int a,int b)
{
  return a*b/__gcd(a,b);
}