먼저 최대공약수(HCF, Highest Common Factor)를 구하는 개념부터 살펴보겠습니다.
최대공약수(HCF)란?
두 개 이상의 수를 각각 나누어 떨어지게 하는 수 중에서 가장 큰 수를 최대공약수(HCF)라고 합니다. 영어로는 Greatest Common Measure(GCM) 또는 Greatest Common Divisor(GCD)라고도 부르며, 한국에서는 일반적으로 '최대공약수'라는 용어를 사용합니다.
예를 들어 다음과 같은 경우를 생각해 볼 수 있습니다.
12와 16의 최대공약수는 무엇일까요?
12의 약수 = 1, 2, 3, 4, 6, 12
16의 약수 = 1, 2, 4, 8, 16
두 수의 공통 약수는 1, 2, 4이며, 그중 가장 큰 값은 4입니다. 따라서 12와 16의 최대공약수(H.C.F)는 4가 됩니다.
최소공배수(LCM)란?
두 정수 x와 y에 대해 최소공배수(LCM(x, y))는 x와 y 모두로 나누어 떨어지는 가장 작은 양의 정수를 의미합니다.
예를 들면 다음과 같습니다.
LCM(2, 3) = 6
LCM(6, 10) = 30
C 프로그램 예제
다음은 유클리드 호제법(Euclidean Algorithm)을 이용해 두 정수의 최대공약수(GCD)를 구하고, 이를 활용해 최소공배수(LCM)까지 계산하는 C 프로그램입니다. 유클리드 호제법은 나머지 연산(%)을 반복하며 두 수의 최대공약수를 효율적으로 찾는 대표적인 알고리즘으로, 시간 복잡도가 매우 낮아 널리 사용됩니다.
#include <stdio.h>
int main() {
int num1, num2, x, y, temp, gcd, lcm;
printf("Enter two integers\n");
scanf("%d%d", &x, &y);
num1 = x;
num2 = y;
/* 유클리드 호제법으로 GCD 계산 */
while (num2 != 0) {
temp = num2;
num2 = num1 % num2;
num1 = temp;
}
gcd = num1;
lcm = (x*y)/gcd;
printf("GCD of %d and %d = %d\n", x, y, gcd);
printf("LCM of %d and %d = %d\n", x, y, lcm);
return 0;
}
코드 동작 원리
프로그램의 핵심 로직은 while 반복문 안에 있습니다. 두 수 중 한쪽(num2)이 0이 될 때까지 나머지 연산을 반복하면서 값을 교환하고, 반복이 끝나면 남은 값(num1)이 바로 최대공약수가 됩니다. 이후 최소공배수는 두 수의 곱을 최대공약수로 나누는 공식 LCM = (x × y) / GCD를 통해 간단히 구할 수 있습니다.
실행 결과
위 프로그램을 컴파일 후 실행하면 다음과 같은 출력을 확인할 수 있습니다.
Run 1:
Enter two integers
6 12
GCD of 6 and 12 = 6
LCM of 6 and 12 = 12
Run 2:
Enter two integers
24 36
GCD of 24 and 36 = 12
LCM of 24 and 36 = 72
첫 번째 실행에서 6과 12를 입력하면 최대공약수 6, 최소공배수 12가 출력되고, 두 번째 실행에서 24와 36을 입력하면 최대공약수 12, 최소공배수 72가 올바르게 계산되는 것을 확인할 수 있습니다.