프로그래머스 'N개의 최소공배수' 문제풀이 후 최대공약수와 최소공배수 알고리즘을 리마인드 할 겸 정리해보았다.

최대공약수

예시

18와 48의 최대공약수는 6이다.

풀이

// 최대공약수 구하기
public int gcd(int a, int b) {
    if (a == 0) {
        return b;
    }

    return gcd(b%a, a);
}

두 숫자의 나머지 연산를 재귀적으로 수행하면 최대공약수를 구할 수 있다. (유클리드 알고리즘)
ex)

18 48
12 18
 6 12
 0  6

최소공배수

최소공배수를 구하기 위해 직접 계산을 하다보면 최대공약수가 필요하다는 것을 알 수 있고
이어서 최소공배수를 구하는 공식도 알게된다.

예시

18과 48의 최소공배수는 144이다.

풀이

// 최소공배수 구하기
public int lcm(int a, int b) {
	return a * b / gcd(a,b);
}

// 최대공약수 구하기
public int gcd(int a, int b) {
    if (a == 0) {
        return b;
    }

    return gcd(b%a, a);
}

공식 : a * b / gcd(a,b)