최대공약수와 최소공배수를 구하는 효율적인 방법

학습 동기

A와 B의 최대공약수를 구하는 알고리즘 문제를 풀었다.

코드 구현

public static void GCD(int A, int B) {
	int gcd = 1;
	for (int i = 2; i <= A && i <= B; i++) {
		if (A % i == 0 && B % i == 0) {
			gcd = i;
		}
	}
	System.out.print(gcd);
}

시간복잡도는 $O(min(A, B))$ 이다.

결과는 시간초과가 발생하였다.. 아무래도 최대공약수를 구하는 더 효율적인 방법이 있는 것 같다.

소인수분해

소인수분해는 다음과 같은 방법으로 최대공약수를 구할 수 있다.

1. 두 자연수를 소인수분해한다.
2. 공통된 소인수를 찾는다.
3. 소인수의 지수 중 작은 수를 찾는다.
4. 거듭제곱을 하여 최대공약수를 구한다.

예시 1

$60, 48$

1. 소인수분해
   $60 = 2^2 \times 3 \times 5\\48 = 2^4 \times 3$
2. 공통된 소인수
   $2$, $3$
3. 지수 중 작거나 같은 수
   $2^2 \times 3$
4. 거듭제곱 = 최대공약수
   $2^2 \times 3 = 12$

코드 구현

public static void GCD(int A, int B) {
	int gcd = 1;
	for (int i = 2; i <= A && i <= B; i++) {
		while (A % i == 0 && B % i == 0) {
			gcd *= i;
			A /= i;
			B /= i;
        }
	}
    System.out.print(gcd);
}

시간복잡도는 $O(min(A, B))$ 이다.

일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 다음에 소개할 유클리드 호제법은 좀더 간단한 방법을 제시한다.

유클리드 호제법

$A$ % $B = R$ $(A \geq B,$ $0 \lt R \lt B)$
A와 B의 최대공약수를 $(A, B)$라고 하면, $(A, B) = (B, R)$이 성립한다.

유클리드 호제법은 다음과 같은 방법으로 최대공약수를 구할 수 있다.

1. $A$ % $B = R$
2. $A = B,$ $B = R \rarr A$ % $B = R$
3. $B = 0$이 되는 순간의 $A$가 최대공약수이다.

예시 1

$(1071, 1029) = (1029, 42) = (42, 21) = (21, 0) = 21$

코드 구현

public static void GCD(int A, int B) {
	while (B != 0) {
		long temp = B;
		B = A % B;
		A = temp;
	}
	System.out.print(A);
}

시간복잡도는 $O(\log{(min(A, B))})$

최대공약수를 활용한 최소공배수 구하기

$LCM(A, B) =$ $A \times B \over GCD(A, B)$

예시 1

$GCD(10 ,5) = (10, 5) = (5, 0) = 5$
$LCM(10, 5) =$ $10 \times 5 \over GCD(10, 5)$ $= 10$

코드 구현

public static void LCM(int A, int B) {
	int lcm = (A * B) / GCD(A, B);
	System.out.print(lcm);
}
public static int GCD(int A, int B) {
	while (B != 0) {
		long temp = B;
		B = A % B;
		A = temp;
	}
	return A;
}

참고자료

• https://mathbang.net/202#gsc.tab=0
• https://namu.wiki/w/%EC%97%B0%EC%A0%9C
• https://cobook.tistory.com/49
• https://calcproject.tistory.com/225
• https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
• https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98