[알고리즘 - Python] BOJ 16563

https://www.acmicpc.net/problem/16563

16563번: 어려운 소인수분해

 

from math import sqrt

_ = int(input())        # 필요 없음
k = list(map(int, input().split()))     # 자연수들
M = max(k)      # 자연수의 최댓값

arr = list(i for i in range(M + 1))     # arr을 초기화 함

for i in range(2, int(sqrt(M)) + 1):
    # 2부터 M의 제곱근까지만 계산해도 됨
    if arr[i] == i:
        # 만약 소수라면
        arr[i] = i
        for j in range(i + i, M + 1, i):
            # 소수의 배수를 전부 다 소수로 초기화 함
            arr[j] = min(arr[j], i)     # 이때 제일 작은 소수로 초기화 해야함

for i in k:
    while i != 1:
        # i가 1이 되지 않을 때 까지 계속 나눠야 함
        print(arr[i], end = ' ')        # arr[i]는 i를 나누는 가장 작은 소수
        i //= arr[i]
    print()

 

 

시간 초과가 오지게 나서 당황했는데, 문제를 곰곰히 생각해보니까 최적화 할 수 있는 부분이 너무 많았다.

 

• 배열의 크기를 5,000,000으로 잡을 필요가 없다.
• 최대 수를 찾아야 하는데, 그냥 변수에 저장하면 되는 일이었다.
• 최대 수까지 에라토스테네스의 수를 계산할 필요가 없이, 최대 수의 제곱근까지만 계산해도 된다.
• 마지막으로 제일 작은 소수로 초기화 하면 logN 시간에 풀 수 있었다....