[백준] 2312번 > 수 복원하기

www.acmicpc.net/problem/2312

2312번: 수 복원하기

문제

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

예제 입력 1

2

6

24

예제 출력 1

2 1

3 1

2 3

3 1

 

---

풀이

나누었을 때 나머지가 0일때만 count해주어서 child_list에 추가시켜줌.

만약 n이 105라면

child_list = [[2, 0], [3, 1], [4, 0], [5, 1], [6, 0], [7, 1]]이 될 것이다.

이중에서 한번도 사용하지 않은 즉 i[1]이 0인 것은 제외하고 출력

t = int(input())
for _ in range(t):
    n = int(input())
    child_list = []
    devide_num = 2
    while n != 1:
        count = 0
        while True:
            if n % devide_num == 0:
                n //= devide_num
                count += 1
            else:
                break
        child_list.append([devide_num, count])
        devide_num += 1
    for i in child_list:
        if i[1]:
            print(*i)