[백준] 16563번 어려운 소인수분해 ★

💡문제접근

• 일반적인 소인수분해 과정을 코드로 작성했으나 시간초과(TLE)가 발생했다.
• 에라토스테네스의 체를 이용해서 소수를 걸러준 다음 소수로 나눠 소인수 분해를 해준다.
• 참, 거짓을 이용하는 에라토스테네스의 체 방법도 있지만 숫자를 넣어 에라토스테네스의 체 방법을 사용할 수 있는 것을 이번 문제를 풀면서 처음 알게 되었다. 구글링해도 나오지 않아서 정말 오랜 시간 고민해서 해결했다.

💡코드(메모리 : 323720KB, 시간 : 4124ms)

import sys
input = sys.stdin.readline

def SieveofEratosthenes(x):
    arr = [i for i in range(x+1)]
    i = 2
    # i의 배수가 x보다 크지 않을 때까지
    while i * i <= x:
        if arr[i] == i:
            for j in range(i*i, x, i):
                if arr[j] == j:
                    arr[j] = i
        i += 1
    return arr

N = int(input())
# 자연수 k의 범위는 2 ≤ k ≤ 5,000,000
temp = SieveofEratosthenes(5000001)
K = list(map(int, input().strip().split()))
for k in K:
    result = []
    while True:
        if k == 1:
            break
        result.append(temp[k])
        k //= temp[k]
    print(" ".join(map(str, result)))

📌시간초과 코드(단순 소인수분해)

import sys
input = sys.stdin.readline

N = int(input())
k = list(map(int, input().strip().split()))

def solve(x):
    t = 2
    while True:
        if x == 1:
            break
        if x % t == 0:
            x //= t
            ans.append(t)
        else:
            t += 1
    return ans

for i in k:
    ans = []
    res = solve(i)
    print(" ".join(map(str, res)))

📌시간초과 코드(에라토스테네스의 체 이용)

import sys
input = sys.stdin.readline

N = int(input())
k = list(map(int, input().strip().split()))

Max = -1
for i in k:
    if Max < i:
        Max = i

arr = [True] * (Max + 1)
prime_number = []
arr[0] = False
arr[1] = False
for i in range(2, int(Max ** 0.5) + 1):
    if arr[i]:
        prime_number.append(i)
        for j in range(i * i, Max + 1, i):
            arr[j] = False


def solve(x):
    while True:
        if x == 1:
            break
        for i in prime_number:
            if x % i == 0:
                x //= i
                ans.append(i)
                break
    return ans


for i in k:
    ans = []
    res = solve(i)
    print(" ".join(map(str, res)))

💡소요시간 : 1h 4m