C++로 두 수의 공약수 개수 구하는 프로그램

개요

이 글에서는 두 수의 공약수 개수를 구하는 방법을 알아보겠습니다. 모든 공약수를 일일이 나열하는 대신, 개수만 효율적으로 세는 것이 핵심입니다. 예를 들어 12와 24의 공약수는 1, 2, 3, 4, 6, 12로 총 6개이므로 정답은 6이 됩니다.

핵심 아이디어

두 수의 공약수는 결국 두 수의 최대공약수(GCD)의 약수와 같습니다. 따라서 먼저 GCD를 구한 뒤, 그 GCD의 약수 개수를 세면 문제가 간단해집니다. 또한 약수를 셀 때 1부터 √GCD까지만 확인하면 되기 때문에 연산량을 크게 줄일 수 있습니다.

알고리즘

countCommonDivisor(a, b)

begin
    count := 0
    gcd := a와 b의 최대공약수
    for i := 1 to square root of gcd, do
        if gcd is divisible by i, then
            if gcd / i = i, then
                count := count + 1
            else
                count := count + 2
            end if
        end if
    done
    return count
end

여기서 주목할 점은 gcd / i == i인 경우입니다. 이는 i가 GCD의 제곱근이라는 의미이며, 같은 약수를 두 번 세지 않도록 1만 더해줍니다. 그 외의 경우에는 i와 gcd/i가 서로 다른 한 쌍의 약수이므로 2를 더합니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a, int b) {
    if (a == 0)
       return b;
    return gcd(b%a, a);
}
int countCommonDivisors(int a,int b) {
    int gcd_val = gcd(a, b); // a와 b의 최대공약수를 구함
    int count = 0;
    for (int i=1; i<=sqrt(gcd_val); i++) {
        if (gcd_val%i==0) { // i가 GCD의 약수인 경우
            if (gcd_val/i == i) // 제곱근인 경우 중복 방지
               count += 1;
            else
               count += 2; // i와 gcd_val/i는 서로 다른 약수
        }
    }
    return count;
}
main() {
    int a = 12, b = 24;
    cout << "Total common divisors: " << countCommonDivisors(a, b);
}

실행 결과

Total common divisors: 6

코드 설명

gcd 함수: 유클리드 호제법을 재귀적으로 구현한 것으로, a가 0이 되면 b가 최대공약수가 됩니다.

countCommonDivisors 함수: 먼저 두 수의 GCD를 구한 후, 1부터 √GCD까지 반복하면서 약수 여부를 검사합니다. 완전제곱수인 경우를 제외하고는 약수가 항상 쌍으로 존재하기 때문에 2씩 증가시킵니다.

시간 복잡도

GCD 계산에 O(log(min(a, b)))의 시간이 걸리고, 약수 개수를 세는 데 O(√GCD)의 시간이 걸립니다. 단순히 1부터 두 수 중 작은 값까지 전부 확인하는 방식(O(n))보다 훨씬 효율적입니다.