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

✔ 문제

---

✔ 풀이

🤢 틀린 코드 (시간 초과)

n = int(input())
nums = []
div = 2

while n >= 0:
    if n % div == 0:
        nums.append(div)
        n = n // div
    else:
        div += 1

print(*nums)

while문 조건이 잘못된 것 같다.

 

👻 정답 코드

n = int(input())
nums = []
div = 2

while n != 1:
    if n % div == 0:
        nums.append(div)
        n = n // div
    else:
        div += 1

print(*nums)

---

✔ 설명

예제 입력1을 보면 72를 입력 받고 2 2 2 3 3 을 출력한다.

1. 72 // 2 = 36 

2. 36 // 2 = 18

3. 18 // 2 = 9

4. 9 // 3 = 3

5. 3 // 3 = 1

 

72는 2로 나눠지므로 2로 나눈 후, 그 몫(36)을 가지고 다시 나눠지는 가장 작은 수(2)를 구하는 패턴이다.

그래서 div를 2로 고정한 후 div로 나눠진다면 nums 리스트에 나눠지는 수를 저장하고 n에는 나눠진 몫을 저장한다.

만약 현재 div로 나눠지지 않는다면 div += 1을 하여 나눠질때까지 계속 반복한다.