N! 에서의 0의 갯수 (소인수분해 응용)

 

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

int main() {
    // freopen
    int n, i, j, tmp, cnt1=0, cnt2=0; 

    scanf("%d", &n);
    for(i=2; i<=n; i++) {
        tmp = i;
        j= 2;
        while(1) {
            if(tmp %j ==0) {
                if(j==2) cnt1++;
                else if(j == 5) cnt2++;
                tmp = tmp/j; // 여기까지 소인수분해
            }
            
            else j++;
            if(tmp == 1) break;
        }
    }
    
    if(cnt1 < cnt2) printf("%d\n", cnt1);
    else printf("%d\n", cnt2);
    
    return 0;
}