두 자연수의 최대공약수 (GCD, Greatest Common Divisor)와 최소공배수 (LCM, Least Common Multiple)의 기본 개념과 이들 간의 관계, 그리고 이를 효율적으로 구하는 방법을 소개합니다.
1. 기본 개념
- 최대공약수 (GCD): 두 수가 공통으로 가지는 약수 중 가장 큰 수
- 최소공배수 (LCM): 두 수가 공통으로 가지는 배수 중 가장 작은 수
이 개념들은 수학 문제뿐만 아니라 프로그래밍 문제에서도 자주 활용됩니다.
2. 핵심 수식 및 알고리즘
(1) 두 수의 곱과 GCD/LCM의 관계
두 자연수 $a$와 $b$에 대해 다음과 같은 관계가 성립합니다.
$$
a \times b = \text{gcd}(a, b) \times \text{lcm}(a, b)
$$
이 식은 한 값(최대공약수 혹은 최소공배수)을 알고 있을 때 나머지 값을 쉽게 구할 수 있는 중요한 관계를 나타냅니다.
(2) 유클리드 알고리즘
최대공약수를 효율적으로 계산하기 위한 방법은 유클리드 알고리즘입니다. 이 알고리즘은 다음과 같은 재귀적 성질에 기반합니다.
$$
\text{gcd}(a, b) = \text{gcd}(b, a \mod b)
$$
단, $b = 0$이면 $a$가 최대공약수가 됩니다.
예시 (a = 48, b = 18):
- $48 \mod 18 = 12$ → 새로운 쌍: (18, 12)
- $18 \mod 12 = 6$ → 새로운 쌍: (12, 6)
- $12 \mod 6 = 0$ → 최대공약수는 6
최소공배수는 위의 곱의 관계를 이용하여 아래와 같이 구할 수 있습니다.
$$
\text{lcm}(a, b) = \frac{a \times b}{\text{gcd}(a, b)}
$$
1.1. 최대공약수 (GCD) 구하기 – 유클리드 알고리즘
아이디어:
두 정수 $a$와 $b$에 대해,
- 만약 $b \neq 0$라면, $a \mod b$의 결과를 이용하여 재귀적으로 GCD를 구할 수 있습니다.
- $b$가 0이 되면, 남은 $a$가 최대공약수가 됩니다.
과정 설명:
- 초기 상태:
두 수 $a$와 $b$를 입력받습니다.
- 반복 과정:
- 종료:
$b = 0$이 되면, 현재 $a$가 두 수의 최대공약수입니다.
예시:
$a = 48$, $b = 18$인 경우,
- $48 \mod 18 = 12$ → (18, 12)
- $18 \mod 12 = 6$ → (12, 6)
- $12 \mod 6 = 0$ → 최대공약수는 6
1.2. 최소공배수 (LCM) 구하기
아이디어:
두 수의 곱과 최대공약수의 관계를 이용합니다.
즉,
$$
\text{lcm}(a, b) = \frac{a \times b}{\text{gcd}(a, b)}
$$
과정 설명:
- 먼저 위에서 구한 최대공약수(gcd)를 구합니다.
- 두 수 $a$와 $b$의 곱을 최대공약수로 나누면 최소공배수를 얻을 수 있습니다.
1.3. 최종 Java 코드 구성
아래 코드는 위 과정을 그대로 반영한 Java 코드입니다. 코드 내 주석을 통해 각 단계의 유도 과정을 함께 확인할 수 있습니다.
public class GCDLCMGuide {
// 유클리드 알고리즘을 이용해 최대공약수를 구하는 메서드
public static int gcd(int a, int b) {
// b가 0이 될 때까지 반복
while (b != 0) {
// 현재 a와 b의 값을 임시 변수에 저장
int temp = b;
// a를 b로, b를 a % b의 결과로 갱신
b = a % b;
a = temp;
}
// 반복 종료 시, a에 최대공약수가 저장됨
return a;
}
// 최대공약수와 두 수의 곱의 관계를 이용해 최소공배수를 구하는 메서드
public static int lcm(int a, int b) {
// 두 수의 곱을 최대공약수로 나누어 최소공배수를 계산
return a * b / gcd(a, b);
}
public static void main(String[] args) {
java.util.Scanner sc = new java.util.Scanner(System.in);
System.out.print("두 자연수를 입력하세요 (공백으로 구분): ");
int a = sc.nextInt();
int b = sc.nextInt();
// 최대공약수와 최소공배수를 구하고 출력
System.out.println("최대공약수: " + gcd(a, b));
System.out.println("최소공배수: " + lcm(a, b));
sc.close();
}
}4. 관련 문제
[[BOJ] 2609.최대공약수와 최소공배수](https://www.acmicpc.net/problem/2609)
문제 설명:
두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 프로그램을 작성하시오.
입력:
– 한 줄에 10,000 이하의 두 자연수가 공백으로 구분되어 주어집니다.
출력:
– 첫째 줄에 최대공약수를, 둘째 줄에 최소공배수를 출력합니다.
아래는 해당 문제의 답이 되는 Java 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
int gcdValue = gcd(n, m);
//gcd
System.out.println(gcdValue);
//lcm
System.out.println(n*m / gcdValue);
}
static int gcd(int n, int m){
int remain = n % m;
if(remain == 0){
return m;
}
return gcd(m, remain);
}
}이 코드에서는 입력받은 두 자연수에 대해
- 첫째 줄에 최대공약수를,
- 둘째 줄에 최소공배수를 출력합니다.
5. 참고 자료
- 유클리드 알고리즘:
고대 그리스 수학자 유클리드가 고안한 효율적인 최대공약수 계산법입니다.
- 수학적 관계:
$$
a \times b = \text{gcd}(a, b) \times \text{lcm}(a, b)
$$
이 관계는 두 수의 곱과 그들의 최대공약수, 최소공배수 사이의 깊은 연관성을 보여줍니다.
- 추가 자료: 위키피디아 – 유클리드 알고리즘