[백준] 11653번 : 소인수분해 - python

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

 

---

• 문제

---

• 설계하기(접근방법) 

1. 정수 n을 입력받는다.

2. 소인수분해 하는법

작은 소수부터 반복적으로 나누며 출력한다. 

더 이상 나눠지지 않으면 다음 소수로 진행한다.

마지막에 몫이 1인 된 순간 종료한다.

 

---

• 코드(출력)

n = int(input())

if (n == 1):
    print('')

for i in range(2, n + 1):
    if (n % i == 0):
        while (n % i == 0):
            n /= i
            print(i)

---

• 얻어갈 부분

1. 처음에 코드를 짤 때 n 보다 작은 소수를 다 구해놓고 n을 소수로 나누었다. 하지만 작은수 i부터 더 이상 나누어 떨어지지 않을 때 까지 진행하면 뒤의 i의 배수는 자동적으로 제거가 되는데 이 사실을 간과해서 시간초과가 일어났다.