[BOJ, 백준] 27725 지수를 더하자 Python

 

1부터 K까지 prime에 해당된 소수를 전부 곱했을 때, 해당 소수(prime)의 지수를 묻는 것과 동일하게 볼 수 있겠다.

이하는 코드가 되겠다.

 

import math
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
prime = list(map(int,input().split())) #prime의 길이가 N
K = int(input())

answer = 0
for i in range (0,N):
    cnt = 0
    num = K
    while num > 1:
        cnt += (num // prime[i])
        num //= prime[i]
    answer += cnt
print(answer)