[백준 Python] - 11653 소인수분해

1. 문제 - 11653번

2. 접근법

소인수분해를 하는 문제의 경우, 고민해보며 두가지 방법을 찾았다.

- 주어진 수 n을 2부터 순차적으로 나누며 확인하는 방법으로 풀거나
- 에라토스테네스의 체로 n 이하의 소수 집합을 구한 후 소수를 순차적으로 나누거나

 <정답 코드 1 : 순차적 소인수 분해>

def prime_factor(num):
    if num == 1:
        print("")

    for i in range(2,num+1):
        while num != 1:
            if num%i == 0:
                print(i)
                num //= i
            else:
                break
        if n == 1:
            break

n = int(input())

prime_factor(n)

<정답 코드 2 : 소수 집합 구한 후 순차적 소인수 분해>

import sys
from math import sqrt
input = sys.stdin.readline

def prime_num(num):
    prime = [True]*(num+1)

    for i in range(2, int(sqrt(num))+1):
        if prime[i]:
            for j in range(2*i, num+1, i):
                prime[j] = False
    
    prime_list = []
    for i, value in enumerate(prime):
        if i!= 0 and i!= 1 and value:
            prime_list.append(i)

    return prime_list

def prime_factor(num):
    prime_list = prime_num(num)
    if n == 1:
       print("")
    for i in prime_list:
        while num != 1:
            if num%i == 0:
                num //= i
                print(i)
            else:
                break
        if num == 1:
           break
               
n  = int(input())

prime_factor(n)

 

이처럼 두가지 방법으로 문제를 풀었는데,
처음 예상대로 코드 실행 시간은 첫번째 방법이 훨씬 짧았다.

굳이 에라토스테네스의 체로 소수 집합을 구하지 않아도 충분히 풀 수 있는 문제이며, 소수 집합을 구하는데 추가적인 시간이 소요되기 때문이다.

이런 문제를 풀 때 특히 주의할 점이 있는데,
그건 바로 1에 대한 처리다. 실수하지 않도록 늘 주의하자.