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

최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나눌 수 있는 수 중에서 가장 큰 수를 의미합니다.

예를 들어, 45와 27이라는 두 수가 있다고 가정해 보겠습니다.

45 = 5 * 3 * 3
27 = 3 * 3 * 3

두 수의 공통 약수는 3과 9이며, 이 중 가장 큰 수는 9입니다. 따라서 45와 27의 최대공약수는 9입니다.

이제 C++을 사용하여 두 수의 GCD를 구하는 다양한 방법을 살펴보겠습니다.

방법 1: 유클리드 호제법(나머지 연산) 활용

가장 널리 사용되는 방식은 유클리드 호제법으로, 나머지 연산자(%)를 이용해 재귀적으로 GCD를 구하는 방법입니다.

예제 코드

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

실행 결과

GCD of 105 and 30 is 15

위 프로그램에서 gcd() 함수는 재귀 함수로 동작하며, 매개변수로 a와 b 두 개를 받습니다. 만약 b가 0이라면 a 값을 그대로 반환하여 main() 함수로 결과를 전달합니다. 그렇지 않은 경우에는 b와 a % b(a를 b로 나눈 나머지)를 인자로 하여 자기 자신을 다시 호출합니다. 핵심 로직은 아래 코드 스니펫과 같습니다.

int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}

방법 2: 반복적인 뺄셈 활용

나머지 연산 대신 뺄셈을 반복하는 방식으로도 GCD를 구할 수 있습니다.

예제 코드

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

실행 결과

GCD of 105 and 30 is 15

위 프로그램 역시 gcd()가 재귀 함수로 구현되어 있으며, a와 b를 매개변수로 받습니다. 동작 방식은 다음과 같습니다.

a 또는 b가 0이면 함수는 0을 반환합니다.
a와 b가 같으면 a를 반환합니다. 이때의 값이 곧 최대공약수입니다.
a가 b보다 크면 a - b와 b를 인자로 하여 재귀 호출합니다.
b가 a보다 크면 a와 b - a를 인자로 하여 재귀 호출합니다.

핵심 로직은 아래 코드 스니펫에 정리되어 있습니다.

int gcd(int a, int b) {
    if (a == 0 || b == 0)
    return 0;
    else if (a == b)
    return a;
    else if (a > b)
    return gcd(a - b, b);
    else return gcd(a, b - a);
}

마무리

두 방법 모두 같은 결과를 출력하지만, 일반적으로 나머지 연산을 사용하는 유클리드 호제법이 뺄셈 방식보다 반복 횟수가 적어 더 빠르게 동작합니다. 따라서 실무에서는 첫 번째 방법을 사용하는 것이 권장됩니다.