C++로 숫자의 완전 제곱수 약수 개수 구하기

이 튜토리얼에서는 주어진 숫자의 모든 완전 약수(perfect divisors)의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.

여기서 '완전 약수'란 약수 중에서 완전 제곱수인 값들을 의미합니다. 예를 들어 16의 약수는 1, 2, 4, 8, 16이며, 이중에서 1(1²), 4(2²), 16(4²)이 완전 제곱수이므로 정답은 3이 됩니다.

접근 방법

효율적인 계산을 위해 다음과 같은 방식을 사용합니다.

1부터 √n까지의 수만 반복하면서 n의 약수 쌍(i와 n/i)을 동시에 확인합니다. 각 약수가 완전 제곱수인지 검사하여 맞다면 카운트를 증가시킵니다. 이때 i와 n/i가 같은 경우 중복으로 세지 않도록 주의해야 합니다.

완전 제곱수 판별은 해당 수의 제곱근을 구한 뒤, 그 값을 다시 제곱했을 때 원래 수와 일치하는지 확인하는 방식으로 처리합니다.

예제 코드

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

// 완전 제곱수 여부 확인
bool if_psquare(int n){
    int sq = (int) sqrt(n);
    return (n == sq * sq);
}

// 완전 약수(완전 제곱수인 약수)의 개수 반환
int count_pdivisors(int n){
    int count = 0;
    for (int i = 1; i * i <= n; ++i){
        if (n % i == 0){
            // i가 완전 제곱수인지 확인
            if (if_psquare(i))
                ++count;
            // 짝이 되는 약수 n/i가 완전 제곱수인지 확인 (중복 제외)
            if (n / i != i && if_psquare(n / i))
                ++count;
        }
    }
    return count;
}

int main(){
    int n = 16;
    cout << "Total perfect divisors of " << n << " = " << count_pdivisors(n) << "\n";
    n = 12;
    cout << "Total perfect divisors of " << n << " = " << count_pdivisors(n);
    return 0;
}

실행 결과

Total perfect divisors of 16 = 3
Total perfect divisors of 12 = 2

결과 분석

n = 16인 경우: 16의 약수는 1, 2, 4, 8, 16입니다. 이 중 완전 제곱수는 1, 4, 16으로 총 3개입니다.

n = 12인 경우: 12의 약수는 1, 2, 3, 4, 6, 12입니다. 이 중 완전 제곱수는 1과 4로 총 2개입니다.

시간 복잡도

이 알고리즘은 √n까지만 반복하기 때문에 시간 복잡도는 O(√n)입니다. 따라서 매우 큰 수에 대해서도 빠르게 완전 약수의 개수를 계산할 수 있습니다.