C++로 팩토리얼을 나누는 수의 최대 거듭제곱 구하기

문제 개요

두 개의 수 n과 fact가 주어졌을 때, fact!(fact의 팩토리얼)를 나눌 수 있는 n의 최대 거듭제곱을 구하는 것이 목표입니다.

예를 들어 fact = 5, n = 2라면 답은 3입니다. 5! = 120이며, 120은 2³ = 8로는 나누어 떨어지지만 2⁴ = 16으로는 나누어지지 않기 때문입니다.

접근 방법: 르장드르 공식(Legendre's Formula)

이 문제는 르장드르 공식을 활용하면 효율적으로 해결할 수 있습니다. 르장드르 공식은 어떤 소수 p가 fact!를 나누는 최대 거듭제곱을 구하는 공식으로, 다음과 같이 표현됩니다.

[fact/p] + [fact/p²] + [fact/p³] + ... ([ ]는 정수 나눗셈)

n이 합성수일 경우에는 먼저 n의 모든 소인수를 찾은 뒤, 각 소인수에 대해 fact!를 나누는 거듭제곱을 계산하고 그 값들을 소인수의 지수로 나눈 후, 그중 최솟값을 구하면 됩니다. 최솟값을 구하는 이유는 가장 부족한 소인수가 전체 나눗셈 가능 횟수를 제한하기 때문입니다.

예시 계산

fact = 146, n = 15라고 가정해 보겠습니다. 15의 소인수는 3과 5입니다.

소수 3의 경우:
[146/3] + [48/3] + [16/3] + [5/3] + [1/3] = 48 + 16 + 5 + 1 + 0 = 70

소수 5의 경우:
[146/5] + [29/5] + [5/5] + [1/5] = 29 + 5 + 1 + 0 = 35

따라서 15¹은 146!을 35번 나눌 수 있으므로, 답은 35가 됩니다.

C++ 구현 코드

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

// 소수 p가 fact!를 나누는 거듭제곱을 구하는 함수 (르장드르 공식)
int getPowerPrime(int fact, int p) {
    int res = 0;
    while (fact > 0) {
        res += fact / p;
        fact /= p;
    }
    return res;
}

// n이 fact!를 나누는 최대 거듭제곱을 구하는 함수
int findMinPower(int fact, int n) {
    int res = INT_MAX;
    for (int i = 2; i <= sqrt(n); i++) {
        int cnt = 0;
        // 같은 소인수가 여러 번 포함된 경우(예: 12 = 2² × 3)까지 고려
        while (n % i == 0) {
            cnt++;
            n /= i;
        }
        if (cnt > 0) {
            int curr = getPowerPrime(fact, i) / cnt;
            res = min(res, curr);
        }
    }
    // 남은 n이 2 이상이면 그 자체가 소수
    if (n >= 2) {
        int curr = getPowerPrime(fact, n);
        res = min(res, curr);
    }
    return res;
}

int main() {
    int fact = 146, n = 15;
    cout << "Minimum power: " << findMinPower(fact, n);
}

실행 결과

Minimum power: 35

시간 복잡도

소인수분해에는 O(√n), 각 소인수에 대한 르장드르 공식 적용에는 O(log_p fact)가 소요되므로, 전체 시간 복잡도는 약 O(√n × log fact)입니다. fact!를 직접 계산하지 않고도 답을 구할 수 있어 매우 큰 fact 값에도 효율적으로 동작합니다.