소인수분해 응용2

자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그 램을 작성하세요. 만약 5!  = 5x4x3x2x1 = 120으로 일의자리부터 연속적된 ‘0’의 개수는 1입니다. 만약 12! = 479001600으로 일의자리부터 연속적된 ‘0’의 개수는 2입니다.

 

▣ 입력설명

첫 줄에 자연수 N(10<=N<=1,000)이 입력된다.

 

▣ 출력설명

소인수 분해한 결과를 출력한다.

 

▣ 입력예제 1

12

 

▣ 출력예제 1

2

 

int형은 2의 31 -1까지밖에 값을 수할수없습니다 따라서 N이 1000까지 N!를 구할수 없습니다

따라서 N까지의 숫자를 소인수 분해하여 소인수분해된 2의 갯수와 5의 갯수를 비교하여 다음문제를 해결해 나갈수 있다

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int two = 0;
	int five = 0;
	int j = 0;
	int tmp = 0;
	int N=0;
	cin >> N;
	vector<int> a(N+1);
	
	for (int i = 2; i <= N; i++)
	{
		tmp = i;
		j = 2;
		while (1)
		{
			if (tmp % j == 0)
			{
				if (j == 2)two++;
				else if (j == 5)five++;
				tmp = tmp / j;
				
			}
			else j++;
			if (tmp == 1)
				break;
		}
	}// 소인수분해
	
	if (two < five)//2의 갯수와 5의 갯수를 비교하여 두개를 곱하여 만들수있는 10의 갯수를 구함 2의갯수가 2개 5의갯수가 3개다 그러면 5가 1개 더 많더라고 총 10을 2개밖에 만들지 못함
		cout << two;
	else
		cout << five;

}