C 프로그램으로 팩토리얼의 후행 0 개수 구하는 방법

팩토리얼의 후행 0이란?

주어진 팩토리얼(factorial) 값에서 후행 0(trailing zero), 즉 결과값 끝에 연속해서 붙어 있는 0의 개수를 구하는 방법을 세 가지 예제를 통해 살펴보겠습니다.

예제로 이해하기

예제 1

입력: 4
출력: 0

설명: 4! = 24이므로 후행 0이 없습니다.

4! = 4 × 3 × 2 × 1 = 24입니다. 일의 자리 숫자가 4이기 때문에 후행 0이 존재하지 않습니다.

예제 2

입력: 6
출력: 1

설명: 6! = 720이므로 후행 0이 하나 있습니다.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720입니다. 일의 자리가 0이므로 후행 0이 정확히 하나 존재합니다.

예제 3

입력은 다음과 같습니다.

n = 4
n = 5

출력은 다음과 같습니다.

4!의 후행 0 개수: 0

5!의 후행 0 개수: 1

후행 0이 생기는 원리

곱셈 결과에서 0이 만들어지려면 10, 즉 2와 5의 곱이 필요합니다. 팩토리얼에는 짝수인 2가 5보다 항상 훨씬 많이 포함되므로, 후행 0의 개수는 사실상 인수 5의 개수에 의해 결정됩니다. 따라서 n!의 후행 0 개수는 다음 공식으로 빠르게 계산할 수 있습니다.

후행 0 개수 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

예를 들어 n = 25일 경우 ⌊25/5⌋ = 5, ⌊25/25⌋ = 1이므로 후행 0은 총 6개입니다.

C 프로그램 코드

다음은 주어진 팩토리얼에서 후행 0의 개수를 찾는 C 프로그램입니다.

#include <stdio.h>
static int trailing_Zeroes(int n){
    int number = 0;
    while (n > 0) {
        number += n / 5;
        n /= 5;
    }
    return number;
}
int main(void){
    int n;
    printf("enter integer1:");
    scanf("%d",&n);
    printf("\n no: of trailing zeroe's of factorial %d is %d\n\n ", n, trailing_Zeroes(n));
    printf("enter integer2:");
    scanf("%d",&n);
    printf("\n no: of trailing zeroe's of factorial %d is %d ", n, trailing_Zeroes(n));
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

enter integer1:5
no: of trailing zeroe's of factorial 5 is 1
enter integer2:6
no: of trailing zeroe's of factorial 6 is 1

프로그램의 핵심 함수인 trailing_Zeroes()는 n을 5로 나눈 몫을 계속 더하고, n을 5로 반복해서 나누는 방식으로 5의 거듭제곱에 해당하는 인수까지 모두 세어 줍니다. 이 알고리즘은 실제 팩토리얼 값을 직접 계산하지 않고도 매우 큰 n에 대해서도 빠르게 후행 0의 개수를 구할 수 있다는 장점이 있습니다.