[알고리즘] LCM

LCM

---

최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 수를 의미합니다.

LCM을 구하는 방법에는 여러 방법이 있지만, 가장 흔히 알려진 방법은 GCD를 이용하는 방법입니다.

 

GCD

---

[알고리즘] GCD - 유클리드 호제법

 

 

LCM 알고리즘

---

두 수 a와 b의 최소 공배수 lcm(a, b)는 다음과 같이 계산됩니다

lcm(a, b) = a × b / gcd(a, b)​

LCM 구현

---

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

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

LCM 시간복잡도

---

lcm의 시간복잡도는 gcd 시간복잡도에 의존합니다.

따라서 lcm의 시간복잡도는 log(min(a, b))입니다.