소인수분해

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

"""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()

• Dependency: teflib.numtheory.prime_factorization_small