최대공약수, 최소공배수를 구하는 방법을 알아보자

최대공약수(GCD)
두 자연수의 공통된 약수 중 가장 큰 수
최소공배수(LCM)
두 자연수의 공통된 배수 중 가장 작은 수

최대공약수

방법1

2부터 min(a, b) 수를 차례로 넣어 확인 -> O(n)

방법2: 유클리드 호제법

GCD(a, b) == GCD(b, a % b)

이 성질을 이용해 a % b == 0이 나올때 까지 반복. 나머지가 0이 되었을 때 나누는 수가 a, b의 최대공약수

코드

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

최소공배수

즉, LCM(a, b) = a * b / GCD(a, b)

코드

int LCM(int a, int b) {
    return a * b / GCD(a, b);
}