BOJ 2312 수 복원하기

https://www.acmicpc.net/problem/2312
시간 2초, 메모리 128MB
input :

• 테스트 케이스의 수
• N (2 ≤ N ≤ 100,000)

output :

• 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력
• 인수가 증가하는 순

---

각 소인수들을 배열에 넣어넣고 나올때 마다 체크를 해서 할 까 했는데.

좋은 카운터를 이용하기로 했다.,
근데 most_common 메소드를 쓰면 가장 많이 나온 인수 순서대로 나오니까.
인수가 증가하는 순서로 나오게 하기 위해 정렬을 해주자.

import sys
from math import sqrt
from collections import Counter

minFactor = [i for i in range(100001)]

for i in range(2, int(sqrt(100001))):
    for j in range(i * i, 100001, i):
        if minFactor[j] == j:
            minFactor[j] = i

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    ret = []
    
    while n > 1:
        ret.append(minFactor[n])
        n //= minFactor[n]
        
    prime_numbers = Counter(ret)
    temp = prime_numbers.most_common()
    temp.sort()
    
    for key, value in temp:
        print(key, value)