C++로 두 수의 최대공약수(GCD/HCF)를 구하는 프로그램

이 튜토리얼에서는 C++을 사용하여 두 수의 최대공약수(GCD)와 HCF(Highest Common Factor, 최대공약수)를 구하는 프로그램을 살펴보겠습니다.

GCD와 HCF는 사실상 같은 개념으로, 두 수가 공통으로 가지는 약수 중 가장 큰 값을 의미합니다. 이 문제에서는 두 개의 숫자가 입력으로 주어지며, 우리의 목표는 해당 두 수의 GCD 또는 HCF를 계산하여 출력하는 것입니다.

구현 방법

아래 코드는 재귀 함수를 활용한 유클리드 호제법(Euclidean Algorithm)의 변형으로 문제를 해결합니다. 로직은 다음과 같습니다.

• 한쪽 수가 0이면, 나머지 수가 곧 GCD입니다.
• 두 수가 같다면 그 값 자체가 GCD입니다.
• a가 b보다 크면 gcd(a-b, b)를, 그렇지 않으면 gcd(a, b-a)를 호출하며 두 수의 차이로 계속 줄여 나갑니다.

예제 코드

#include <iostream>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   if (b == 0)
      return a;
   if (a == b)
      return a;
   if (a > b)
      return gcd(a-b, b);
   return gcd(a, b-a);
}
int main(){
   int a = 98, b = 56;
   cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
   return 0;
}

실행 결과

GCD of 98 and 56 is 14

동작 원리 설명

위 예제에서 a = 98, b = 56일 때의 실행 흐름은 다음과 같습니다.

1. gcd(98, 56) → 98 > 56이므로 gcd(42, 56) 호출
2. gcd(42, 56) → 42 < 56이므로 gcd(42, 14) 호출
3. gcd(42, 14) → 42 > 14이므로 gcd(28, 14) 호출
4. gcd(28, 14) → gcd(14, 14) 호출
5. gcd(14, 14) → 두 수가 같으므로 14 반환

따라서 98과 56의 최대공약수는 14입니다.

참고로 위 차감 기반 방식은 이해하기 쉽지만 큰 수에 대해서는 반복 횟수가 많아질 수 있습니다. 실무에서는 나머지 연산(%)을 사용하는 gcd(b, a % b) 방식이 더 효율적이므로 상황에 맞게 선택하시기 바랍니다.