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

이 튜토리얼에서는 두 수의 최대공약수(HCF, Highest Common Factor)를 구하는 프로그램을 다룹니다.

두 개의 숫자가 주어졌을 때, 두 수가 공통으로 가지는 약수 중 가장 큰 값을 찾아 반환하는 것이 목표입니다. 최대공약수는 GCD(Greatest Common Divisor)라고도 부르며, 재귀 함수를 활용하면 간단하게 구현할 수 있습니다.

예시 코드

#include <stdio.h>
// 재귀 호출을 통해 HCF(최대공약수)를 구하는 함수
int gcd(int a, int b){
    if (a == 0 || b == 0)
        return 0;
    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;
    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
    return 0;
}

실행 결과

GCD of 98 and 56 is 14

동작 원리

위 프로그램은 재귀적 뺄셈 방식을 사용합니다. 두 수가 같아질 때까지 작은 수를 큰 수에서 반복해서 빼며 진행되고, 두 수가 같아지는 시점의 값이 바로 최대공약수입니다.

98과 56의 경우 다음과 같이 진행됩니다.

• gcd(98, 56) → gcd(42, 56)
• gcd(42, 56) → gcd(42, 14)
• gcd(42, 14) → gcd(28, 14)
• gcd(28, 14) → gcd(14, 14)
• 두 수가 같아지므로 결과는 14

실제로 98의 약수는 1, 2, 7, 14, 49, 98이고, 56의 약수는 1, 2, 4, 7, 8, 14, 28, 56입니다. 따라서 공통 약수 중 가장 큰 값인 14가 최대공약수가 됩니다.

참고로 입력값 중 하나라도 0이면 최대공약수를 정의할 수 없으므로 0을 반환하도록 처리했습니다. 더 빠른 성능이 필요하다면 나머지 연산(%)을 이용한 유클리드 호제법을 사용하는 것이 좋습니다.