악곱 == 악성곱슬

수학, 에라토스테네스의 체

---

해당 문제는 N! 을 구한 뒤 아래 자리수에 있는 0의 개수를 세는 문제이다. 0의 개수를 세기위해서 말 그대로 N!을 구해서 풀 수 있다. 하지만 N의 개수가 500이므로 500의 팩토리얼을 직접 구하는 것은 너무 큰 수를 다루게 된다.

따라서 2 x 5의 개수를 세면 된다. 따라서 소인수 분해를 하여 2의 개수와 5의 개수중 최소값을 반환하면 된다. 소인수 분해를 하기 위해 우선 에라토스테네스의 체 알고리즘을 이용하여 N까지의 소수를 구한다. 이를 이용해 N까지 반복하여 소인수 분해를 하며 사전 자료형에 하나씩 카운트 해준다.

코드는 아래와 같다.

import sys

# 에라토스테네스의 체
def prime_sieve(sieve_size):
    sieve = [True] * (sieve_size + 1)
    sieve[0] = False
    sieve[1] = False
    for i in range(2, int(sieve_size**0.5) + 1):
        if sieve[i] is False:
            continue
        for j in range(i**2, sieve_size+1, i):
            sieve[j] = False
    primes = []
    for i in range(sieve_size + 1):
        if sieve[i]:
            primes.append(i)
    return primes

def get_prime_number(n):
    prime_list = prime_sieve(n)
    factors = dict()
    # 소수 리스트 돌면서
    for i in range(2, n + 1):
        for p in prime_list:
            count = 0
            # 나눠지면 나눈다.
            while i % p == 0:
                i /= p
                # 몇번 나누었는지 카운트 하고
                count += 1
            if count > 0:
                try:
                    factors[p] += count
                except:
                    factors[p] = count
    return factors

def solution(n):
    if N < 5:
        print(0)
    else:
        result = get_prime_number(n)
        print(min(result[2], result[5]))

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    solution(N)