[알고리즘][C++] N!에서 0의 개수

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;


//int main(){ 
//	//freopen("input.txt", "rt", stdin);
//	int n, i, res=1, cnt=0, max=-2147000000;
//	scanf("%d", &n);
//	for(i=2; i<=n; i++){ 
//		res = res * i;
//	}
//	while(res>0){
//		if(res%10==0) {
//			cnt++;
//			if(cnt>max) max=cnt;
//		}
//		else cnt=0;
//		res = res/10;
//	}
//	printf("%d", max);
//	
//	return 0;
//}
//오버플러우 발생..  -> 소인수 분해 활용. 2와 5의 갯수를 세면 된다 

int main(){ 
	//freopen("input.txt", "rt", stdin);
	int n, i, j, tmp, two=0, five=0, cnt=0;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){ 
		tmp=i;
		j=2;
		while(1){
			if(tmp%j==0) { 
				tmp=tmp/j; 
				if(j==2) two++;
				else if(j==5) five++;  
			}
			else j++; 
			if(tmp==1) break; 
		}
	}
	
	if(two<five) printf("%d\n", two);
	else printf("%d\n", five);
	
// 굳이 따로 계산하지 않아도 된다 
//	while(five>0){
//		two--;
//		five--;
//		cnt++;
//	}
//	printf("%d\n", cnt);
	

	
	return 0;
}

 

n! 을 직접 다 계산해서 구하려고 하면 int 범위를 넘어서므로 특정 숫자 이상은 결과값이 제대로 출력되지 않는다 

 

-> 소인수 분해하는 방법을 이용해서 2와 5의 개수를 세서 최소값을 출력하면 된다!