[백준 코딩테스트(Python)] 기본 수학 2 - 소인수분해

11653번: 소인수분해

---

문제

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

 

입력

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

 

출력

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

 

---

1. 문제 접근 방식

처음에 작성한 코드는 이중 for문에 if문, while문까지 다양하게 다 사용해서 작성하였다. 그 결과 시간초과....

코드를 짜면서도 이것보다 훨~씬 간단하게 작성하는 방법이 있을 텐데라는 생각이 들었다.

고민 끝에 결국은 구글링을 해봄..

 

처음 작성한 코드

## 시간 초과
N = int(input())

lst = []
for i in range(1, N+1):
    count = 0
    for j in range(1, i+1):
        if i % j == 0:
            count += 1
    if count == 2:
        while N > 1:
            if N % i == 0:
                N = N // i
                lst.append(i)
            else:
                break
print(*lst, sep ='\n')

 

우선, 코드가 매우 짧았다.

그래서 더더욱 이해하기가 쉬웠고, if문 안에 while문을 사용할 생각을 해본 적도 없는데 이 코드를 통해서 알게 되었다.

 

1) N이 1인 경우에는 아무것도 출력하지 않는다 (출력 조건에 있음)

if N == 1:
    print('')

 

2) 2~N까지의 수(i) 중에서 N을 나누었을 때 떨어지는 수를 구한다. 

여기서 중요한 포인트는, i가 여러 번 나올 수 있게 해야 한다는 것이다.

 

우선 for문을 사용하여 2부터 N까지의 수가 반복될 수 있도록 한 후,

if문으로 N을 i로 나누었을 때 떨어지는 수에 한하여 while문을 진행한다.

⭐while문 가장 중요⭐

while문으로 하나의 i로 N을 최대한 나눌 수 있을 만큼 반복한다. N이 i로 계속 나누어진다면 그만큼 반복을 하고 i 출력 후 N은 i로 나누어준다.

만약, while문 없이 if문에서 코드를 진행한다면, 하나의 i는 딱 한 번만 N을 나눌 수 있다.

예를 들면, 12의 경우 2*2*3으로 2로 12를 2번 나눌 수 있는데, while문이 없다면 2로는 1번만 나눌 수 있다.

for i in range(2, N+1):
    if N % i == 0:
        # 하나의 i로 N을 최대한 나눌 수 있을 만큼 반복하기
        while N & i == 0:
            print(i)
            N = N / i

 

2. 풀이 코드

N = int(input())

# N이 1인 경우 아무것도 출력하지 않음
if N == 1:
    print('')

# 2 ~ N까지의 수(i) 중에서 N을 나누었을 때 떨어지는 수 구하기
for i in range(2, N+1):
    if N % i == 0:
        # 하나의 i로 N을 최대한 나눌 수 있을 만큼 반복하기
        while N & i == 0:
            print(i)
            N = N / i

 

3. REFERENCE

[백준 알고리즘] 11653번 소인수분해 _ 파이썬 python