[2312] 수 복원하기 (Python)

[문제]

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

2312번: 수 복원하기

---

알고리즘 분류는 수학, 정수론, 소수 판정, 에라토스테네스의 체 입니다.

파이썬의 dictionary에는 key, value 형태로 들어가므로 인수와 인수가 곱해진 수를 넣어야 합니다.

---

[코드]

import sys


def prime(n):
    dt = dict()
    p = 2
    while p <= n:
        if n % p == 0:
            dt[p] = dt.get(p, 0) + 1
            n /= p
        else:
            p += 1

    for k, v in dt.items():
        print(k, v)


T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    prime(N)