最大公約数(Greatest Common Divisor, GCD)を求める関数は、ユークリッドの互助法をもちいて、つぎのように実装できる。

  // (a > b を仮定)
  int gcd(int a, int b)
  {
    while (b)
      {
int tmp = a % b;
a = b;
b = tmp;
      }

    return a;
  }

最小公倍数(Least Common Multiple, LCM)を求める関数は、GCDをつかって、つぎのように実装できる。

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

それぞれオーバーフローに注意。特にlcmの分子はかけ算があるので、あふれやすい。

最小公倍数 - Wikipedia