C++에서 n!에 포함된 소수 p의 거듭제곱 구하는 방법

문제 소개

이 문제에서는 숫자 n과 소수 p가 주어집니다. 우리의 목표는 n!에 포함된 소수 p의 거듭제곱을 구하는 것입니다.

문제를 이해하기 위해 예시를 살펴보겠습니다.

입력 : n = 6, p = 2
출력 : 4

문제 접근 방법

가장 직관적인 방법은 n!의 값을 직접 계산한 후 소인수분해하여, 그 결과에서 소수 p가 몇 번 곱해졌는지 세는 것입니다.

예를 들어 5! = 120 = 2 × 2 × 2 × 3 × 5이므로, 5!에 포함된 2의 거듭제곱은 3입니다.

팩토리얼은 다음과 같이 정의됩니다.

n! = n × (n−1) × (n−2) × … × 2 × 1

이제 n = 6, p = 2인 경우를 살펴봅시다.

6! = 1 × 2 × 3 × 4 × 5 × 6 = 720

720을 소인수분해하면 2 × 2 × 2 × 2 × 3 × 3 × 5가 됩니다.

따라서 6!에 포함된 2의 거듭제곱은 4이며, 출력값 역시 4입니다.

효율적인 해법 : 르장드르 공식

n!을 직접 계산하면 값이 매우 빠르게 커져 오버플로우가 발생할 수 있습니다. 대신 르장드르 공식(Legendre's Formula)을 사용하면 n!을 계산하지 않고도 답을 바로 구할 수 있습니다.

르장드르 공식은 다음과 같습니다.

거듭제곱 = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …

즉, n 이하의 수 중 p의 배수 개수, p²의 배수 개수, p³의 배수 개수를 차례로 더하면 됩니다. p의 배수는 최소 한 개의 인자 p를 기여하고, p²의 배수는 여기에 하나를 더 기여하는 원리입니다.

n = 6, p = 2인 경우 : ⌊6/2⌋ + ⌊6/4⌋ + ⌊6/8⌋ = 3 + 1 + 0 = 4

이 알고리즘의 시간 복잡도는 O(log_p n)으로 매우 효율적입니다.

예제 코드

아래 C++ 프로그램은 위 알고리즘의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int powerOfPrimeNfactorial(int N, int P){
   int primePower = 0;
   int factVal = P;
   while (factVal <= N) {
      primePower += N / factVal;
      factVal = factVal * P;
   }
   return primePower;
}

int main(){
   int N = 6;
   int P = 2;
   cout << N << "!에서 소수 " << P << "의 거듭제곱은 " << powerOfPrimeNfactorial(N, P) << endl;
   return 0;
}

실행 결과

6!에서 소수 2의 거듭제곱은 4