28. N!에서 0의 개 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include<stdio.h>
#include<vector>

using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	
	vector<int> prime(n+1, 0);
	vector<int> count(n+1, 0);
	
	int idx = 1;
	for(int i = 2; i <= n; i++)
	{
		bool flag = true;
		for(int j = 2; j*j <= i; j++)
		{
			if(i % j == 0)
			{
				flag = false;
				break;
			}
		}
		if(flag)
		{
			prime[idx] = i;
			idx++;
		}
	}
	
	for(int i = n; i >= 2; i--)
	{
		int _idx = 1;
		int x = i;
		while(x > 1)
		{
			if(x % prime[_idx] == 0)
			{
				count[_idx]++;
				x /= prime[_idx];
			}
			else
				_idx++;
		}
	}
	
	
	if(count[1] >= count[3])
		printf("%d", count[3]);
	else
		printf("%d", count[1]);
		
	return 0;
}

1. 27번 문제인 소수표현방법과 같은 방법이다.

2. 같은 방법으로 실행한 뒤, 연속되는 0의 개수를 찾을 때 2와 5의 사용횟수를 확인하고 더 적은 사용횟수를 출력한다.

10으로 최대 나누기 가능 횟수를 구하는 것이다.