[BOJ] 2312 수 복원하기 Python

import math
from collections import defaultdict
#에라토스테네스 체 응용
num = [i for i in range (0,100001)]
num[0] = 1
prime = []
for i in range (2,int(math.sqrt(100001))+ 1):
    if num[i] == i:
        for j in range (i,100001,i):
            if num[j] == j:
                num[j] = i

N = int(input())
for i in range (0,N):
    x = int(input()) #소인수분해 되는 숫자
    d = defaultdict(int)
    while num[x] != 1:
        d[num[x]] += 1
        x //= num[x]
    d_key = list(d.keys())
    for j in range (0,len((d_key))):
        print(d_key[j], d[d_key[j]])

 

에라토스테네스 체의 응용으로 간단하게 풀 수 있습니다.