BAEKJOON 11653 - 소인수분해

BAEKJOON 11653 - 소인수분해

---

◎ Problem Definition

---

◎ Implementation

1. Problem Type 

 - Implementation, Math (Silver 5)

2. Problem Analysis

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

- 소인수분해 : 소수들의 곱으로 분해하는 것 

- 2부터 순차적으로 소수로 나누자. 

3-1. Solution_1 (☆초기 접근)

▶ 완성 코드 

# bj_impl_11653_prime_factors

N = int(input())   #  N (1 ≤ N ≤ 10,000,000)

# primes = []
flag = True
while flag : 
    for n in range(2, N+1):
        if N % n == 0 : 
            print(n)
            #primes.append(n)
            N = int(N / n)
            if N == 1:
                flag = False
            break

▶ 성능 

• 시간초과. 채점 불가 

3-2. Solution_2 

▶ 완성 코드 

코드는 간단한데 시간초과에 걸려 채점이 안된다. 앞서 해본 전체 소수 구하기를 적용해서 다시 해본다. 

N = int(input())   #  N (1 ≤ N ≤ 10,000,000)
prime_flag = [False, False] + [True] * (N-1)
while N > 1 : 
    for n in range(2, N+1):
        if N % n == 0 and prime_flag[n] == True:
            print(n)
            N = N // n
            break

▶ 성능 

• memory: 186928 KB
• Time : 1232 msec 

4. Solution_3 (★공개된 다른 코드 참조)

▶ 완성 코드

# bj_impl_11653_prime_factors
# Trial # 3 : Refered somnus @ baekjoon_11653

N = int(input())
i = 2
r = int(N ** 0.5)

while i <= r :
    while not N % i:  # N % i ==0 
        print(i)
        N //= i
    i += 1
if n > 1:
    print(N)

▶ 성능

• memory: 30864 KB
• Time : 72 msec 

---

◎ Results

- 이 문제에서는 별도의 소수 list를 보유하는 것보다 바로바로 값을 나누어가면서 나누어떨어지는 수들을 출력해주는 방법이 수행시간 측면에서 비교할 수 없을 만큼 훨씬 효율적이었다.