[수학, 정수론] BOJ 9693 시파르

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

9693번: 시파르

 

문제 해결 알고리즘

 

1~N까지 모든 수를 2와 5로 나눠보면서 N!에 있는 2와 5의 개수를 찾고 둘 중 작은 수를 출력해준다.

 

소스 코드

 

 

#include <bits/stdc++.h>
using namespace std;

int main(){
	
	int cnt = 1;
	
	while(true){
		int two_cnt = 0, five_cnt = 0;
		int N; cin >> N;
		if(N == 0) break;
		
		for(int i=1;i<=N;i++){
			int n = i;
			while(true){
				if(n % 2 != 0) break;
				n/=2;
				two_cnt++;
			}
			
			n = i;
			while(true){
				if(n % 5 != 0) break;
				n/=5;
				five_cnt++;
			}
		}
		
		cout << "Case #" << cnt << ": " << min(five_cnt, two_cnt) << '\n';
		cnt++;
	}
}