[python] 팩토리얼 0의 개수

백준 1676번

문제 설명

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

풀이

소인수분해를 해 보면 2와 5의 개수가 0의 개수임을 알 수 있다.
2x5가 몇 개인지를 찾으면 정답을 알 수 있는데
5의 개수는 항상 2의 개수보다 적기 때문에 우리는 5의 개수만 세어주면 된다.
n의 값이 500까지이기 때문에
n을 5부터 5씩 곱해서 125까지 나눈 값을 모두 더해주면 된다.
625부터는 500을 넘기니 계산할 필요가 없다.
이제 보니 코드를 걍 for문 돌려서 짜면 됐는데 왜 저렇게 짰지... 여튼 정답.

제출 코드

import sys

n = int(sys.stdin.readline())

cnt1 = (n // 5)
cnt2 = (n // 25)
cnt3 = (n // 125)

result = cnt1 + cnt2 + cnt3

print(result)