C++로 완전제곱수 만들기: 나눠야 할 최소 수 구하는 방법

어떤 수 N이 주어졌을 때, N을 어떤 수로 나누었을 때 결과가 완전제곱수가 되도록 하는 최소의 수를 구하는 문제를 살펴보겠습니다. 예를 들어 N = 50이라면 답은 2입니다. 50 ÷ 2 = 25이고, 25는 5²에 해당하는 완전제곱수이기 때문입니다.

문제 해결 접근법

어떤 수가 완전제곱수가 되려면 모든 소인수의 지수가 짝수여야 합니다. 즉, 서로 다른 소인수의 등장 횟수가 모두 짝수일 때 그 수는 완전제곱수입니다. 이 성질을 활용하면 다음 순서로 문제를 해결할 수 있습니다.

1. N을 소인수분해합니다.
2. 각 소인수의 지수(거듭제곱된 횟수)를 구합니다.
3. 지수가 홀수인 소인수들을 모두 곱한 값이 바로 N을 나누어야 할 최소의 수입니다.

예를 들어 108 = 2² × 3³이므로 지수가 홀수인 소인수는 3 하나뿐입니다. 따라서 108을 3으로 나누면 36 = 6²이 되어 완전제곱수가 됩니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;

int findMinimumNumberToDivide(int n) {
    int prime_factor_count = 0, min_divisor = 1;

    // 2를 먼저 처리
    while (n % 2 == 0) {
        prime_factor_count++;
        n /= 2;
    }
    if (prime_factor_count % 2)
        min_divisor *= 2;

    // 3부터 sqrt(n)까지 홀수만 검사
    for (int i = 3; i <= sqrt(n); i += 2) {
        prime_factor_count = 0;
        while (n % i == 0) {
            prime_factor_count++;
            n /= i;
        }
        if (prime_factor_count % 2)
            min_divisor *= i;
    }

    // 남은 n이 2보다 크면 그 자체가 홀수 지수의 소인수
    if (n > 2)
        min_divisor *= n;

    return min_divisor;
}

int main() {
    int n = 108;
    cout << "Minimum number to divide is: " << findMinimumNumberToDivide(n) << endl;
}

실행 결과

Minimum number to divide is: 3

코드 동작 원리

이 알고리즘은 전형적인 시행 나눗셈(trial division) 기반의 소인수분해 기법을 사용합니다. 먼저 2로 나눌 수 있는 만큼 반복해서 나누며 지수를 세고, 지수가 홀수라면 결과값에 2를 곱합니다. 이후 3부터 √n까지 홀수에 대해서만 같은 과정을 반복하여 불필요한 연산을 줄입니다. 마지막으로 남은 값이 2보다 크다면 그 값 자체가 지수 1(홀수)인 소인수이므로 결과에 곱해줍니다.

시간 복잡도

√N까지만 검사하면 되므로 시간 복잡도는 O(√N)입니다. N의 크기가 크지 않다면 매우 빠르게 동작하며, 소인수의 지수 패턴만 파악하면 되기 때문에 완전탐색보다 훨씬 효율적입니다.