팩토리얼에서 끝에 붙는 0의 개수 구하기

1. 숫자의 끝에 0이 붙는다는 것은 그만큼 10을 곱했다는 소리다.

2. 10 = 2×5. 소인수의 경우 2보다 5가 차지하는 비율이 적다. 따라서 소인수 5의 개수만 구할 수 있으면 된다.

3. 팩토리얼을 구성하는 소인수 5의 개수는 n/5를 반복해서 합산하는 것으로 구할 수 있다.

• 첫 번째 n/5는 5^1가 있는 수
• 두 번째 n/5는 5^2가 있는 수
• 세 번째 n/5는 5^3가 있는 수
• 예시) 75!의 경우 75/5 = 15이고, 15 / 5 = 3이므로 0의 개수는 18개가 된다.

4. ×5의 개수를 구하는 코드는 아래와 같다.

void FactorialTrailingZeroes(int n)
{
	int ret = 0;
	while(n > 0)
	{
		ret += n / 5;
		n /= 5;
	}
	return ret;
}

※ 재귀함수로 구현한다면 한 줄로도 구현할 수 있다.

void FactorialTrailingZeroes(int n)
{
	return n < 5 ? 0 : trailingZeroes (n / 5) + n / 5;
}