C/C++로 팩토리얼(계승) 값의 후행 0 개수 구하기

후행 0을 세는 기본 원리

팩토리얼(계승) 값에서 후행 0(trailing zero), 즉 숫자 맨 뒤에 붙은 0의 개수를 구하는 핵심 원리는 소인수 중 2와 5가 몇 쌍이나 만나는지를 세는 것입니다. 2와 5가 곱해지면 10이 되고, 이 10 하나당 결과값 끝에 0이 하나씩 추가되기 때문입니다.

예시로 이해하기

7! = 5040이므로 후행 0은 1개입니다.

위 논리를 적용해 보면, 7! = 2 × 3 × 4 × 5 × 6 × 7을 소인수로 분해할 때 2는 3개, 5는 1개가 나옵니다. 2와 5를 짝지으면 한 쌍만 남으므로 후행 0의 개수 역시 1개가 되는 것입니다.

효율적인 계산 방법

팩토리얼 전개 과정에서는 2가 5보다 훨씬 자주 등장하므로, 후행 0의 개수는 사실상 인수 5의 개수에 의해 결정됩니다. 따라서 n을 5, 25, 125처럼 5의 거듭제곱으로 차례대로 나눈 몫을 모두 더하면 됩니다. n ÷ 5는 5의 배수 개수를, n ÷ 25는 5를 두 개 가진 수의 개수를 의미하기 때문입니다.

C/C++ 구현 코드

#include <iostream>
using namespace std;
int main() {
    int n = 45;
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;
    cout << "No of trailing 0s in " << n << "! is " << count;
    return 0;
}

이 코드는 n = 45일 때 45 ÷ 5 = 9, 45 ÷ 25 = 1을 더해 총 10을 출력합니다. 반복문은 n을 i로 나눈 몫이 1 이상일 때까지 i를 5배씩 늘려가며 진행됩니다.

출력 결과

No of trailing 0s in 45! is 10