[백준] 11653 파이썬 (소인수분해)

나의 시간 초과 코드

• 코드

n = int(input())
list = []

#n보다 작은 소수들을 리스트에 넣기
for i in range(2, n+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        list.append(i)

#n이 소수로 나눠지면 나누기 (n이 1이 될 때까지 반복)
while n!=1:
    for i in list:
        if n%i == 0:
            n = n/i
            print(i)
            break

• 풀이
  나는 n을 입력 받고
  n보다 작은 소수들을 구해서 list에 담았다.

  for j in range(2,int(i**0.5)+1):
          if i%j==0:
              break
      else:
          list.append(i)

  안에 있는 for문의 range가 2부터 int(i**0.5)+1 인 이유는
  어떤 자연수에 약수의 개수는 제곱근을 기준으로 대칭이기 때문이다.
  예를 들면, 12의 약수는 1,2,3,4,6,12 (6개)인데
  루트12(=3.xx)보다 박은 수가 3개이고, 큰 수가 3개이다.

  그 다음 n이 1이 될 때까지 소수로 나누었다.
  그런데 이런식으로 했더니 시간 초과가 떴다,,,,;;;

정답 코드

• 코드

n = int(input())
i = 2
while n!=1:
    if n%i == 0:
        print(i)
        n = n/i
    else:
        i+=1

• 풀이
  굳이 소수를 구해서 나누지 말고
  '나눠지는 가장 작은 수'를 구하면 된다.