[BOJ] 1676 :: 팩토리얼 0의 개수

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

n!이 몇개의 0으로 이루어져있는지를 구하는 문제입니다.

10은 2와 5의 곱으로 이루어지는데 상식적으로..? 2의 개수보다 5의 개수가 훨씬 많으므로 소인수 분해 한 결과 5가 몇개인지 탐색해주면 됩니다.

5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 ...이렇게 해서 총 몇개의 5로 이루어져 있는지 구하면 그 결과가 정답입니다.

#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int cnt = 0;
	for (int i = 5; i <= n; i*=5)
	{
		for (int j = 5; j <= n; j++)
		{
			if (j % i == 0)
				cnt++;
		}
	}
	cout << cnt << endl;

}