테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 어려운 소인수분해 ======

===== 풀이 =====
  * [[ps:소인수분해]]에서 설명한것처럼, n이하의 모든 수에 대해서 최소인수를 계산해놓으면, n이하의 임의의 수를 O({소인수갯수}) 로 소인수분해할수 있다.
  * 모든 수의 최소인수를 계산하는 것은 에라토스테네스의 체를 변형해서 O(nloglogn)에 구할수도 있고, linear sieve를 이용해서 O(n)에 구할수도 있다. 시간복잡도는 거의 비슷하지만, 최적화를 최대한 열심히 했을때 실행 속도는 linear sieve쪽이 좀더 빨랐다.
  * 어떤수 x의 소인수의 개수는 대략 O(loglogn)이다. 따라서 m개의 쿼리에 대해서 계산하는 것은 O(mloglogn).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 16563. 어려운 소인수분해".

- Problem link: https://www.acmicpc.net/problem/16563
- Solution link: http://www.teferi.net/ps/problems/boj/16563

Tags: [Number theory] [Linear sieve]
"""


def least_prime_factor(n):
    lpf = list(range(n + 1))
    lpf[2::2] = [2] * (n // 2)
    primes = []
    for i in range(3, n // 3 + 1, 2):
        if lpf[i] == i:
            primes.append(i)
        for p in primes:
            if i * p > n or p > lpf[i]:
                break
            lpf[i * p] = p
    return lpf


def main():
    N = int(input())  # pylint: disable=unused-variable
    k = [int(x) for x in input().split()]

    lpf = least_prime_factor(max(k))
    for k_i in k:
        answer = []
        n = k_i
        while n > 1:
            p = lpf[n]
            n //= p
            answer.append(p)
        print(*answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}