최소공배수(Least Common Multiple)를 언어로 구현하기

1. 최소공배수

• Least Common Multiple, 줄여서 LCM이라고 한다.
• 두 수 또는 여러 수의 공배수 중 가장 작은 양의 정수를 의미한다.
• 최소공배수는 최대공약수(GCD)를 이용해 구할 수 있다.

lcm(a, b) = a * b / gcd(a, b)

여러 수의 최소공배수는 앞에서부터 두 수씩 최소공배수를 누적해서 구하면 된다. 예를 들어 3, 7, 9, 28의 최소공배수는 먼저 3과 7의 최소공배수를 구하고, 그 결과와 9의 최소공배수를 다시 구하는 식으로 계산한다.

---

2. 구현

아래 예제는 유클리드 호제법으로 최대공약수를 구한 뒤, 이를 이용해 배열에 들어 있는 수들의 최소공배수를 계산한다.

public class LeastCommonMultiple {
	long get(int[] num) {
		long min = 0;
		long max = 0;
		long result = num[0];
		int thisNum = 0;

		for (int inx = 1; inx < num.length; inx++) {
			thisNum = num[inx];
			max = Math.max(result, thisNum);
			min = Math.min(result, thisNum);
			result = max * min / gcd(max, min);
		}

		return result;
	}

	long gcd(long i, long j) {
		if (i > j) {
			if (j == 0)
				return i;
			else
				return gcd(j, i % j);
		} else {
			return gcd(j, i);
		}
	}

	public static void main(String[] args) {
		LeastCommonMultiple lcm = new LeastCommonMultiple();
		int[] ex = { 3, 7, 9, 28 };
		System.out.println("result=" + lcm.get(ex));
	}
}

3. 실행 결과

result=252

테스트할 때는 서로소인 수, 같은 약수를 가지는 수, 이미 배수 관계에 있는 수를 함께 넣어 보면 좋다. 예를 들어 3과 7처럼 서로소인 경우에는 두 수의 곱이 최소공배수가 되고, 9와 28처럼 공약수가 없는 수 역시 곱이 최소공배수가 된다. 위 예제에서는 이 값을 차례대로 누적해 최종 결과로 252를 얻는다.