C++로 두 개 이상의 숫자(또는 배열)의 최대공약수(GCD) 구하기

이번 글에서는 두 개 이상의 숫자에 대한 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법을 알아보겠습니다. 두 숫자의 GCD를 구하는 것은 비교적 간단하지만, 세 개 이상의 숫자가 대상이 되면 GCD의 결합 법칙(associativity rule)을 활용해야 합니다.

예를 들어 {w, x, y, z} 네 숫자의 GCD를 구한다고 가정해 봅시다. 이 경우 다음과 같은 단계로 계산이 진행됩니다.

{w, x, y, z} → {gcd(w,x), y, z} → {gcd(gcd(w,x), y), z} → 최종적으로 gcd(gcd(gcd(w,x), y), z)

즉, 앞의 두 수의 GCD를 구한 뒤 그 결과와 다음 수의 GCD를 반복적으로 구하는 방식입니다. 이러한 로직은 배열을 사용하면 매우 간단하게 구현할 수 있습니다.

알고리즘

gcd(a, b) — 두 수의 최대공약수

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

유클리드 호제법(Euclidean algorithm)을 재귀적으로 적용하여 두 수의 GCD를 구합니다. a가 0이면 b가 곧 최대공약수이며, 그렇지 않으면 a를 b를 a로 나눈 나머지와 함께 재귀 호출합니다.

getArrayGcd(arr, n) — 배열 전체의 최대공약수

begin
    res := arr[0]
    for i in range 1 to n-1, do
        res := gcd(arr[i], res)
    done
    return res;
end

배열의 첫 번째 요소를 초기값으로 설정한 후, 두 번째 요소부터 마지막 요소까지 차례대로 현재 결과값과의 GCD를 누적하여 계산합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
int getArrayGcd(int arr[], int n) {
    int res = arr[0];
    for(int i = 1; i < n; i++) {
        res = gcd(arr[i], res);
    }
    return res;
}
main() {
    int arr[] = {4, 8, 16, 24};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "GCD of array elements: " << getArrayGcd(arr, n);
}

실행 결과

GCD of array elements: 4

위 예제에서 배열 {4, 8, 16, 24}의 모든 요소를 나누어 떨어지게 하는 가장 큰 수는 4이므로, 프로그램은 4를 출력합니다. 이 방식은 배열의 크기에 관계없이 선형 시간 복잡도 O(n × log(max)) 내에서 동작하므로 효율적입니다.