C++로 구하는 최소 무제곱 약수 개수

문제 설명

정수 N이 주어졌을 때, 제곱 인수가 없는 약수(무제곱 약수)의 최소 개수를 구하는 것이 목표입니다.

여기서 N의 인수분해 결과는 반드시 완전제곱수가 아닌 약수들로만 구성되어야 합니다.

예시

예를 들어 N = 24라면, 다음과 같이 3개의 무제곱 인수로 분해할 수 있습니다.

인수 = 2 × 6 × 2

각 인수 2, 6, 2는 모두 완전제곱수가 아니므로 조건을 만족하며, 이 경우가 가능한 최소 개수입니다.

알고리즘 접근 방법

• √N 이하의 모든 소수를 먼저 찾습니다.
• √N 이하의 각 소수에 대해, 해당 소수가 N에서 가지는 최대 지수를 구합니다. (예: 24에서 2의 최대 지수는 3)
• 어떤 소인수가 N에서 지수가 1보다 크다면, 그 소인수를 스스로와 곱해 묶을 수 없습니다. (예: 24에서 2의 지수가 3이므로 2×2=4 또는 2×2×2=8은 완전제곱수 또는 완전제곱수를 약수로 포함하게 되어 사용할 수 없습니다.)
• 반면 서로 다른 소인수를 한 번씩만 곱한 값은 어떤 완전제곱수로도 나누어 떨어지지 않으므로 안전하게 하나의 약수로 묶을 수 있습니다.
• 이러한 성질로부터, 정답은 N의 모든 소인수 중 최대 지수의 최댓값이라는 결론을 얻을 수 있습니다.

C++ 구현 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1005

void getPrimes(vector<int>& primes) {
    bool prime[MAX];
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p < MAX; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i < MAX; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p < MAX; p++)
        if (prime[p])
            primes.push_back(p);
}

int getMinimumSquareFreeDivisors(int n) {
    vector<int> primes;
    getPrimes(primes);
    int maxCnt = 0;
    for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
        if (n % primes[i] == 0) {
            int tmp = 0;
            while (n % primes[i] == 0) {
                tmp++;
                n /= primes[i];
            }
            maxCnt = max(maxCnt, tmp);
        }
    }
    if (maxCnt == 0)
        maxCnt = 1;
    return maxCnt;
}

int main() {
    int n = 24;
    cout << "Minimum number of square free divisors = "
         << getMinimumSquareFreeDivisors(n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum number of square free divisors = 3

코드 설명

• getPrimes 함수: 에라토스테네스의 체를 이용해 MAX(1005) 미만의 모든 소수를 미리 구해 벡터에 저장합니다.
• getMinimumSquareFreeDivisors 함수: √N 이하의 소수로 N을 나누어 보며 각 소인수의 지수를 계산하고, 그중 최댓값을 반환합니다.
• maxCnt == 0 처리: N이 소수이거나 1인 경우 소인수의 지수가 계산되지 않으므로, 이때는 답을 1로 설정합니다.

이 알고리즘의 시간 복잡도는 소수 생성에 O(MAX log log MAX), 인수 분해에 O(π(√N))이 소요되어 매우 효율적입니다.