https://tmdrl5779.tistory.com/95

백준 2004번

def countNum(N, num):
    count = 0
    divNum = num
    while(N >= divNum):
        count = count + (N // divNum)
        divNum = divNum * num  # num이 지수배로 증가해서 처음에는 num이 1개, 다음은 2개
    return count

이런식으로 2의 갯수를 구하는 것을 알 수 있었는데….

사실 이 식만봤을때 뭔소린지 이해를 못했다…

8! = 8 7 6 5 4 3 2 1 => 2가 나오는 횟수 7번이다

왜냐

8 = 2x2x2

6 = 2x3

4 = 2x2

2 = 2x1

으로 2가 7번나온다.

제곱수인 4는 2가 2번

3제곱수인 8은 2가 3번 나오는 것을 알 수있다.

여기서 알수있는것이 먼저 8 7 6 5 4 2 1에서 2의 배수의 갯수를 구한다. 8/2 = 4

다음으로 제곱수에 대해서 배수를 구한다. 8/(2*2) = 2

다음으로 세제곱수에 대해서 배수를 구한다. 8/(222) = 1

즉 4 + 2 + 1이란 것이다.

한번더 100으로 예시를 들면….

100!을 생각해 봤을 때, 5가 곱해진 개수를 생각해보자. 일단 100까지의 수 중에서 5의 배수들이 5를 가지고 있음을 알고 있다. 100까지의 5의 배수는 20개 이므로 100/5=20을 먼저 구한다. 여기서 5의 지수가 2인 애들을 보면 5^2의 배수들이 5를 하나씩 더 가지고 있음을 알 수 있다 따라서 기존에 20에다가 100/5^2=4 를 더해준다.