[BOJ/Python] 2312_수 복원하기

문제 출처 : https://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

 

---

풀이

 

정수를 소인수분해 하는 문제이다. 소인수분해 하기 위해서는 우선 소수의 리스트를 구해야 한다.

소수 리스트를 구하기 위해 에라토스테네스의 체를 이용하였다. 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법으로, 체를 통해 무언가를 걸어내듯이 소수의 배수들을 차례로 걸러내어 남은 수들이 소수임을 이용한 방법이다.

에라토스테네스의 체 (사진 출처 : 위키백과)

 

import sys
 
numbers = [True for _ in range(100000)]
numbers[0]=False
numbers[1]=False
prime_number=[]
 
for i in range(2,100000):
    if numbers[i]:
        prime_number.append(i)
        for j in range(i*2,100000,i):
            numbers[j] = False
 
n = int(sys.stdin.readline())
for _ in range(n):
    num = int(sys.stdin.readline())
    
    for i in prime_number:
        if num==1:
            break
        count = 0
        while num%i == 0: 
            num = num//i
            count +=1
        if count>0:
            print(i,count)

 

1. 문제에서 소인수분해할 수의 범위가 10만까지라고 했으니, 10만까지의 소수를 구하했다.
2. 소수를 구하기 위해 에라토스테네스의 체를 이용하였다. 우선 0,1을 제외하고 나머지는 모두 True로 설정하였다.
3. 반복문을 통해 만약 현재 수(index)가 True라면 소수 리스트(prime_number 리스트)에 추가하고, 그 수의 배수들을 모두 False로 처리한다.
4. 반복문이 끝나면 최종적으로 prime_number 리스트에는 10만 이하의 소수들이 저장되어있다.
5. 이를 이용하여 입력받은 수(num)를 소인수분해한다.
6. for문을 이용하여 소수를 2,3,5,7,9의 순서로 하나씩 꺼내어 num이 나누어 떨어지면 나누어떨어지지 않을때까지 나누는 과정을 num이 1이 될때까지 반복한다.