ﾕﾕﾕﾕﾕ

webエンジニアです

最大公約数を利用して最小公倍数を求める

C++ TIL

「最大公約数」と問われると「ユークリッドの互除法！」とただちに着想が湧くようにはなってきた。

　その一方で「最小公倍数」と問われたら、「おや...」と思いながら調べ直さざるをえない自分がいた。

　この記事できちんと整理して、記憶に定着させたい。

定理

正整数に{\displaystyle a}, {\displaystyle b}に対して、{\displaystyle a}と{\displaystyle b}の最大公約数{\displaystyle \mathrm {gcd} (a,\ b)}と最小公倍数{\displaystyle \mathrm {lcm} (a,\ b)}との間には {\displaystyle \mathrm {gcd} (a,\ b)\cdot \mathrm {lcm} (a,\ b)=ab} という関係がある。1

実践

　つまりAとBの最小公倍数LCMは、AとBの最大公約数GCDを使ってこう書ける。

{\displaystyle \mathrm {lcm} (a,\ b)=\frac{ab} {\mathrm {gcd} (a,\ b)}}

　要するに、まずは最大公約数をユークリッドの互除法で求めてから、単純計算で最小公倍数を求めればよい。{\displaystyle A \geq B} として、

#include <iostream>

int main() {
  int A = 24, B = 18;
  int a = A, b = B, r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }

  int gcd = b;
  int lcm = A * B / gcd;

  printf("%d\n", lcm);
  return 0;
}

　全体の計算量はユークリッドの互除法の計算量に従って O(logn) となる。

  1. https://ja.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0↩