16563. 어려운 소인수분해

이름값하는 문제!

 

처음에는 에라토스테네스의 체를 그대로 이용해서 소수 목록을 만들고, 그 소수 목록의 값을 하나씩 꺼내가며 구하는 방식을 생각했으나...

답은 나오는데 계속 시간 초과가 떴다.

 

다른 방법은 이렇다.

각 숫자가 어떤 소인수를 가지고 있는지 알 수 있도록 해야 한다. 예를 들면 9는 3을 가지고 있도록! 

가장 작은 소인수를 기억해 놓으면 원래의 숫자에서 거슬러 올라가며 소인수를 모두 가져올 수 있다. 

 

import sys
input = sys.stdin.readline

def era(n) :
    check = [0 for _ in range(n+1)]
    for i in range(2, n+1) :
        if check[i] != 0 :
            continue
        for j in range(i, n+1, i) :
            if check[j] != 0 :
                continue
            check[j] = i
    return check

def trace(n, check) :
    ans = []
    while n != 1 :
        ans.append(check[n])
        n//=check[n]
    print(' '.join(map(str, ans)))

n = int(input())
numbers = list(map(int, input().split()))
check = era(max(numbers))
for num in numbers : 
    trace(num, check)

 

나중에 다시 풀어도 바로 성공 못할 거 같다. 다시 풀어봐야지