백준 11653 파이썬 - 소인수분해

1. 문제 링크

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

11653번: 소인수분해

---

2. 나는 어떻게 생각했는가? 

n = int(input())
case = []
devider = 2

while n > 1:
  if n % devider == 0:
    case.append(devider)
    n = n / devider
  else:
    devider += 1
    if devider > n:
      break

for i in range(len(case)):
  print(case[i])

 

---

3. 코드 개선

- 맞았지만 시간이 오래 걸린다. 

- 백준에서는 언어마다 보너스 시간이 있기 때문에 맞았다고 나왔지만, 2초이상 걸린것은 확실하다. 

- 수행시간이 짧은 다른분들의 코드를 살펴보니, 0.5를 곱해서 범위를 반으로 줄여서 푸는 분들이 있었다.

- 왜 0.5를 곱하는 건지 이해가 안되어 백준에 질문을 올렸다. (답변이 생기면 추후 업데이트 하겠습니다)

 

import sys

N = int(sys.stdin.readline().rstrip())
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        print(i)
        N //= i
if N > 1:
    print(N)

 

- 위의 코드를 제출해보면, 보이는 바와 같이 수행시간이 엄청 빨라진 것을 확인할 수 있다. 

- 이게 왜 가능한 것인지 이해가 잘 가지 않는다. 

 

 

[질문에 대한 답변]

소인수 분해를 하는 것이기 때문에, 어떤 수 N을 나누는 수는 제곱근 이상으로 값이 필요하지 않기 때문에 

제곱근을 하여 i의 범위를 지정한 것이다.