C++로 숫자의 팩토리얼에서 후행 0 개수 구하기

정수 하나가 입력으로 주어지며, 목표는 그 숫자의 팩토리얼(계승)을 계산했을 때 결과값 뒤에 붙는 0의 개수를 구하는 것입니다. 숫자 N의 팩토리얼은 [1, N] 범위에 속하는 모든 정수의 곱으로 정의됩니다.

후행 0이 만들어지는 원리

어떤 수의 끝자리에 0이 붙으려면 그 수가 10의 배수여야 하며, 이는 곧 소인수로 2와 5의 짝을 가진다는 의미입니다. 5보다 큰 수의 팩토리얼을 소인수분해해 보면 2의 개수가 항상 5의 개수보다 많습니다. 따라서 숫자를 5의 거듭제곱으로 나누어 보면 인수 중 5의 개수를 알 수 있고, 이 5의 개수가 곧 후행 0의 개수와 같습니다.

예시 1

입력

number=6

출력

숫자의 팩토리얼에서 후행 0의 개수: 1

설명

팩토리얼 값은 30입니다.
30의 소인수 : 2 * 3 * 5
(2, 5) 짝이 하나뿐이므로 후행 0은 1개입니다.

예시 2

입력

number=12

출력

숫자의 팩토리얼에서 후행 0의 개수: 2

설명

팩토리얼 값은 479001600입니다.
479001600의 소인수 : 2¹⁰ × 3⁵ × 5² × 7 × 11
(2, 5) 짝이 두 개이므로 후행 0은 2개입니다.

알고리즘 접근 방식

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다. 주어진 숫자를 5의 거듭제곱으로 반복해서 나누되, 나눈 몫이 1 이상이면 그만큼 5가 존재한다는 뜻이므로 이 값을 카운트에 누적합니다.

정수 하나를 입력받습니다.
trailing_zeros(int number) 함수는 숫자를 받아 그 팩토리얼의 후행 0 개수를 반환합니다.
카운트 변수를 0으로 초기화합니다.
for 루프를 사용해 숫자를 5의 거듭제곱으로 나눕니다.
number/i 값이 1 이상이면 그 값을 카운트에 더합니다.
루프가 끝나면 카운트를 결과로 반환합니다.

C++ 코드 예제

#include <iostream>
using namespace std;
int trailing_zeros(int number){
    int count = 0;
    for (int i = 5; number / i >= 1; i *= 5){
        int temp = number / i;
        count = count + temp;
    }
    return count;
}
int main(){
    int number = 50;
    cout<<"숫자의 팩토리얼에서 후행 0의 개수: "<<trailing_zeros(number);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

숫자의 팩토리얼에서 후행 0의 개수: 12