[백준] 11653번 소인수분해 - Python / 알고리즘 기초 1/2 - 수학 1 (참고)

---

---

---

💡 문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

💭 접근

1보다 큰 자연수를 소수들의 곱으로 나타내는 것을 소인수분해라고 한다. 이런 점을 활용해 2부터 n까지의 수로 나누는데, 나머지가 0이 아닐 때까지 나눠주면서 지나가야 한다.

---

🔥 내가 작성한 코드

# 처음엔 소수문제니까 당연히 에라토스테네스의 체 알고리즘을 
# 사용해야 할 줄 알았다.
def seive_of_eratosthenes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i**2, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

n = int(input())

prime = seive_of_eratosthenes(n)
for num in prime:
    while n % num == 0:
        print(num)
        n //= num

📒 코드

n = int(input())

if n == 1:
    print('')

for i in range(2, n + 1):
    while n % i == 0:
        print(i)
        n //= i

---

💭 후기

처음 풀이땐 소수를 활용하는 문제니까 당연히 에라토스테네스의 체 알고리즘을 사용해서 입력받은 수보다 작은 소수를 모두 구한 뒤 나누기를 하였다.
그러나 어차피 나머지가 0이 아닐때까지 나누는 것이므로, 어떤 소수의 거듭제곱까지 모두 나눠진다는 것을 생각하지 못하였다.

(아래가 처음 풀이, 위가 다시 푼 코드)

시간과 메모리 역시 많이 줄어든 것을 볼 수 있다.

---

🔗 문제 출처

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

---