C/C++로 숫자 팩토리얼의 후행 0 개수 계산하기

이 글에서는 임의의 숫자에 대한 팩토리얼(계승) 결과에서 후행 0(끝자리 0)의 개수를 계산하는 방법을 살펴보겠습니다. 예를 들어 n = 5이면 5! = 120이므로 후행 0은 하나뿐입니다. 20!의 경우 20! = 2432902008176640000이므로 후행 0은 4개입니다.

문제 접근 방식

가장 간단한 방법은 실제로 팩토리얼 값을 계산한 뒤 0의 개수를 세는 것입니다. 하지만 이 방법은 n의 값이 커지면 오버플로우가 발생하여 실패하게 됩니다. 따라서 우리는 다른 접근 방식을 사용해야 합니다.

핵심 아이디어는 다음과 같습니다. 후행 0은 곱셈 과정에서 소인수 2와 5가 짝을 이룰 때 발생합니다. 즉, 2 × 5 = 10이 만들어질 때마다 끝자리에 0이 하나씩 추가됩니다. 팩토리얼 전개에서 2의 개수는 항상 5의 개수보다 많기 때문에, 5의 개수만 세면 후행 0의 개수를 구할 수 있습니다.

후행 0의 개수 = factorial(n)의 소인수 중 5의 개수

예를 들어 25!의 경우 25, 20, 15, 10, 5에서 각각 5가 등장하며, 25는 5 × 5이므로 5를 두 번 기여합니다. 이를 일반화하면 n을 5, 25, 125... 로 나눈 몫을 모두 더하면 됩니다.

알고리즘

countTrailingZeros(n)

begin
   count := 0
   for i := 5, (n/i) >= 1, increase i := i * 5, do
      count := count + (n / i)
   done
   return count;
end

예제 코드

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
int countTrailingZeros(int n) {
   int count = 0;
   for (int i = 5; n / i >= 1; i *= 5)
      count += n / i;
   return count;
}
main() {
   int n = 20;
   cout << "Number of trailing zeros: " << countTrailingZeros(n);
}

실행 결과

Number of trailing zeros: 4

이 알고리즘의 시간 복잡도는 O(log₅ n)으로 매우 효율적입니다. n이 아무리 커도 팩토리얼 값을 직접 계산하지 않고도 후행 0의 개수를 빠르게 구할 수 있다는 것이 가장 큰 장점입니다.