Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 배우는 최대공약수(GCD) 계산: 중학교 방식(Middle School Procedure) 완벽 가이드

이번 튜토리얼에서는 중학교 방식(Middle School Procedure)을 이용해 두 수의 최대공약수(GCD, Greatest Common Divisor) 또는 최대공약수(HCF, Highest Common Factor)를 구하는 C++ 프로그램을 다룹니다.

두 개의 정수가 주어졌을 때, 해당 값들의 소인수분해를 통해 공통 인수를 찾고, 그중 지수가 가장 작은 항들을 곱하여 최대공약수를 계산하는 것이 이 방식의 핵심 원리입니다.

알고리즘의 기본 원리

중학교 시절 수학 시간에 배운 소인수분해 방법을 그대로 활용합니다. 예를 들어 10과 15의 최대공약수를 구한다면:

  • 10 = 2 × 5
  • 15 = 3 × 5
  • 공통 인수는 5이므로, GCD(10, 15) = 5

프로그램은 다음 순서로 동작합니다.

  1. 각 숫자를 소인수분해하여 밑수(factor)와 지수(exponent)를 구조체에 저장합니다.
  2. 소인수분해 결과를 화면에 출력합니다.
  3. 두 수의 공통 인수를 비교하며, 공통 인수의 지수 중 작은 값을 곱해 나가 최대공약수를 구합니다.

예제 코드

#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;

// 소인수분해 결과를 저장하는 구조체
typedef struct {
    int size;
    int factor[MAXFACTORS + 1];
    int exponent[MAXFACTORS + 1];
} FACTORIZATION;

// 소인수분해를 수행하는 함수
void FindFactorization(int x, FACTORIZATION* factorization) {
    int i, j = 1;
    int n = x, c = 0;
    int k = 1;
    factorization->factor[0] = 1;
    factorization->exponent[0] = 1;
    for (i = 2; i <= n; i++) {
        c = 0;
        while (n % i == 0) {
            c++;
            n = n / i;
        }
        if (c > 0) {
            factorization->exponent[k] = c;
            factorization->factor[k] = i;
            k++;
        }
    }
    factorization->size = k - 1;
}

// 소인수분해 결과를 출력하는 함수
void DisplayFactorization(int x, FACTORIZATION factorization) {
    int i;
    cout << "Prime factor of " << x << " = ";
    for (i = 0; i <= factorization.size; i++) {
        cout << factorization.factor[i];
        if (factorization.exponent[i] > 1)
            cout << "^" << factorization.exponent[i];
        if (i < factorization.size)
            cout << "*";
        else
            cout << "\n";
    }
}

// 중학교 방식으로 GCD를 구하는 함수
int gcdMiddleSchoolProcedure(int m, int n) {
    FACTORIZATION mFactorization, nFactorization;
    int r, mi, ni, i, k, x = 1, j;
    FindFactorization(m, &mFactorization);
    DisplayFactorization(m, mFactorization);
    FindFactorization(n, &nFactorization);
    DisplayFactorization(n, nFactorization);
    int min;
    i = 1;
    j = 1;
    while (i <= mFactorization.size && j <= nFactorization.size) {
        if (mFactorization.factor[i] < nFactorization.factor[j])
            i++;
        else if (nFactorization.factor[j] < mFactorization.factor[i])
            j++;
        else {
            min = mFactorization.exponent[i] > nFactorization.exponent[j]
                      ? nFactorization.exponent[j]
                      : mFactorization.exponent[i];
            x = x * mFactorization.factor[i] * min;
            i++;
            j++;
        }
    }
    return x;
}

int main() {
    int m = 10, n = 15;
    cout << "GCD(" << m << ", " << n << ") = "
         << gcdMiddleSchoolProcedure(m, n);
    return (0);
}

코드 설명

1. FACTORIZATION 구조체

소인수분해 결과를 저장하기 위해 factor(밑수) 배열과 exponent(지수) 배열, 그리고 유효한 항목의 개수를 나타내는 size 변수로 구성된 구조체를 정의했습니다.

2. FindFactorization 함수

2부터 시작해 순서대로 나누어 떨어지는지 검사하며 소인수분해를 진행합니다. 같은 소수로 여러 번 나누어질 경우, 나눈 횟수만큼 지수가 증가합니다.

3. gcdMiddleSchoolProcedure 함수

두 수의 소인수 목록을 앞에서부터 비교해 나갑니다. 두 목록에 동일한 소인수가 등장하면, 두 지수 중 더 작은 값을 선택하여 결과값에 누적으로 곱합니다. 모든 공통 인수에 대해 이 과정을 마치면 최종적으로 최대공약수를 얻게 됩니다.

실행 결과

Prime factor of 10 = 1*2*5
Prime factor of 15 = 1*3*5
GCD(10, 15) = 5

실행 결과를 보면 10은 2와 5로, 15는 3과 5로 분해되며, 공통 인수인 5가 최대공약수로 출력됩니다.

마무리

중학교 방식은 유클리드 호제법(Euclidean Algorithm)보다 직관적이지만, 큰 수를 다룰 때는 소인수분해 비용 때문에 효율이 떨어질 수 있습니다. 그럼에도 불구하고 알고리즘 학습 초기 단계에서 GCD의 수학적 개념을 코드로 구현해 보기에 매우 좋은 예제입니다.