문제
유클리드 호제법(Euclid's Algorithm)을 구현하여 두 정수의 최대공약수(GCD)와 최소공배수(LCM)를 구하고, 입력받은 두 정수와 함께 결과를 출력하는 C 프로그램을 작성해 보겠습니다.
유클리드 호제법이란?
유클리드 호제법은 두 수의 최대공약수를 구하는 가장 고전적이고 효율적인 알고리즘입니다. 큰 수를 작은 수로 나눈 나머지를 구하고, 이 나머지와 작은 수를 다시 나누는 과정을 반복하다가 나머지가 0이 되면 그때의 나누는 수가 곧 최대공약수가 됩니다.
또한 최소공배수는 다음 관계식을 이용해 간단히 구할 수 있습니다.
LCM = (두 수의 곱) ÷ GCD
해결 방법
두 정수의 GCD와 LCM을 구하는 핵심 로직은 다음과 같습니다. 먼저 입력값 중 하나라도 0이면 계산이 불가능하므로 종료하고, 그렇지 않으면 재귀 함수를 호출하여 결과를 출력합니다.
if(firstno*secondno!=0){
gcd=gcd_rec(firstno,secondno);
printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
}
실제로 유클리드 호제법을 수행하는 재귀 함수는 다음과 같습니다. 두 번째 인자(y)가 0이 되면 첫 번째 인자(x)가 최대공약수이므로 이를 반환하고, 그렇지 않으면 나머지 연산을 이용해 자기 자신을 다시 호출합니다.
int gcd_rec(int x, int y){
if (y == 0)
return x;
return gcd_rec(y, x % y);
}
프로그램
다음은 유클리드 호제법을 이용해 두 정수의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 전체 C 프로그램입니다.
#include<stdio.h>
int gcd_rec(int,int);
void main(){
int firstno,secondno,gcd;
printf("Enter the two no.s to find GCD and LCM:");
scanf("%d%d",&firstno,&secondno);
if(firstno*secondno!=0){
gcd=gcd_rec(firstno,secondno);
printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
}
else
printf("One of the entered no. is zero:Quitting\n");
}
/* 유클리드 호제법 함수 */
int gcd_rec(int x, int y){
if (y == 0)
return x;
return gcd_rec(y, x % y);
}
참고: 표준 C 규격에서는 main 함수의 반환형으로 void 대신 int를 사용하는 것이 권장됩니다. 또한 이 프로그램은 입력값 중 하나가 0인 경우 0으로 나누는 오류를 방지하기 위해 실행을 종료하도록 처리하고 있습니다.
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과를 확인할 수 있습니다.
Enter the two no.s to find GCD and LCM:4 8 The GCD of 4 and 8 is 4 The LCM of 4 and 8 is 8
4와 8의 경우 최대공약수는 4, 최소공배수는 8로 올바르게 계산된 것을 볼 수 있습니다. 이처럼 유클리드 호제법은 재귀 호출 몇 줄만으로도 최대공약수를 손쉽게 구할 수 있는 강력한 알고리즘입니다.