====== 소인수분해 ======

===== 풀이 =====
  * 말 그대로 [[ps:소인수분해]]를 하는것이 전부인 문제.
  * n의 범위가 10^7로 크지 않으므로, [[ps:소인수분해#Trial division]]으로 충분하다. 시간복잡도는 O(sqrt(n))

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11653. 소인수분해".

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

Tags: [Math]
"""

from teflib import numtheory


def main():
    N = int(input())
    for p, k in numtheory.prime_factorization_small(N).items():
        for _ in range(k):
            print(p)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_factorization_small|teflib.numtheory.prime_factorization_small]]


{{tag>BOJ ps:problems:boj:실버_5}}