[백준] 1676번 팩토리얼 0의 개수 c++

0의 개수에 영향을 미치는 것은

1~n까지의 숫자 중에서,

각 숫자가 갖는 5와 2의 개수이다.

왜냐면 소수 5와 2가 곱해질때 만이 10이 만들어지기 때문이다.

 

따라서 각 숫자의 소인수 중 2와 5의 개수를 카운팅한다음

10이 얼마나 만들어 지는지를 찾는다. -> min(2의 개수, 5의 개수)

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int n;
    cin >> n;

    int a=0, b=0, count=0;
    for (int i = 1; i <= n; i++)
    {
        int num = i;
        while(num%5 == 0){
            num /= 5;
            a++;
        }
        while(num%2 == 0){
            num /= 2;
            b++;
        }
    }
    count = min(a, b);
    cout << count << "\n";
}