시파르

• 팩토리얼 0의 개수 과 같은 문제. 르장드르 공식을 이용해서 N!을 소인수분해했을때 5의 지수를 구하면 된다. 시간복잡도는 O(logn)

"""Solution code for "BOJ 9693. 시파르".

- Problem link: https://www.acmicpc.net/problem/9693
- Solution link: http://www.teferi.net/ps/problems/boj/9693

Tags: [number theory]
"""

import sys
from teflib import psutils


def exponent_of_prime_in_factorial(n: int, p: int):
    """Compute largest power of a prime p that divides factorial(n)."""
    count = 0
    while n:
        n //= p
        count += n
    return count


@psutils.run_until_all_zero
@psutils.testcase_format('Case #{}: ')
def main():
    N = int(sys.stdin.readline())
    print(exponent_of_prime_in_factorial(N, 5))


if __name__ == '__main__':
    main()