백준 11653 소인수 분해

문제 접근

굉장히 간단한 문제이다. 하지만 이를 생각없이 for문을 사용해서 풀려고 하다가 시간복잡도가 기하급수적으로 늘어나는 경험을 했다. 경험적으로 반복문에서 반복에 쓰이는 변수(for문에서 i)가 연속적인 수로 줄어드는 것이 아니라면 그냥 while문을 사용하는 것이 더 현명하다는 것을 깨달았다. 굉장히 간단하고 쉬운 문제였지만 출력의 형태로 인해 정답이 선뜻 생각나지 않았다.

 

문제 풀이

N = int(input())
num = 2
while N > 1:
  if N % num == 0:
    print(num)
    N //= num #나누어 떨어지므로 다음 수는 하나의 소수를 나눈 값을 조사한다
    num = 2 #2부터 탐색을 한다
  else:
    num += 1 #나뉘지 않는다면 다음 수를 조사한다