[백준 1676]- 팩토리얼 0의 개수(C++)

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 처음에는 값을 직접 구한 뒤 0의 개수를 뒤에서부터 세려고 했는데 500!의 값은 굉장히 크다. 아래 사이트에서 구해본 결과

https://ko.numberempire.com/factorialcalculator.php

팩토리얼 계산기

 

 팩토리얼의 값이 너무 크다. 그래서 구글링을 한 결과 소인수 분해를 한 뒤 5의 수를 세면 된다. 예제 출력을 보면 10을 입력받으면 2를 출력해야 하는데 10의 경우 10 9 8 7 6 5 4 3 2 1 에서 10과 5에 5가 한번씩 들어가기 때문에 2가 출력되는 것이다. 이러한 방식으로 값을 구해야 한다. 코드는 아래와 같다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	int sum = 0;
	for (int i = 1; i <= T; i++) {
		int save = i;
		int count = 0;
		while (save % 5 == 0) {
			save /= 5;
			count++;
		}
		if (count != 0) {
			sum += count;
		}
	}
	cout << sum;
}