C++로 n! 속 소수 r의 거듭제곱 구하는 방법

문제 개요

이 문제에서는 두 정수 n과 r이 주어지며, 우리의 목표는 n! (n의 팩토리얼) 안에 포함된 소수 r의 거듭제곱을 구하는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력 − n = 6, r = 2

출력 − 4

설명 −

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
720 = 24 × 32 × 5, 따라서 2의 거듭제곱은 4

효율적인 접근 방법

가장 단순한 해결책은 팩토리얼 값을 직접 계산한 후 소수의 거듭제곱을 세는 것입니다. 하지만 이 방법은 n이 커질수록 연산량이 급격히 늘어나고, 오버플로우가 발생할 위험도 있어 실용적이지 않습니다.

훨씬 더 효율적인 방법은 르장드르 공식(Legendre's Formula)을 활용하는 것입니다.

n!에서 'r'의 거듭제곱 = ⌊n/r⌋ + ⌊n/r²⌋ + ⌊n/r³⌋ + ...

즉, n을 r의 거듭제곱으로 나눈 몫들을 모두 더하면 됩니다. 각 항은 n 이하의 수 중 해당 거듭제곱의 배수인 수의 개수를 의미하며, 배수일수록 소수 인자를 하나 더 기여하기 때문입니다.

예제 코드

위 해결 방법을 C++로 구현한 프로그램입니다.

#include <iostream>
using namespace std;
int primePower(int n, int r) {
    int count = 0;
    for (int i = r; (n / i) >= 1; i = i * r)
        count = count + n / i;
    return count;
}
int main() {
    int n = 6, r = 2;
    cout<<"소수 "<<r<<"의 "<<n<<"! 내 거듭제곱 : "<<primePower(n, r);
    return 0;
}

출력 결과

소수 2의 6! 내 거듭제곱 : 4

동작 원리

코드는 r부터 시작하여 매번 r을 곱해가며 반복합니다. 각 단계에서 n/i는 n 이하의 수 중 i의 배수 개수를 나타내며, 이를 모두 누적하면 n!에 포함된 소수 r의 총 지수를 얻을 수 있습니다. 이 방법은 시간 복잡도가 O(log_r n)으로 매우 효율적입니다.