백준 [11653.소인수분해] | Python

✏️ 문제

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

11653번: 소인수분해

 

✏️ 풀이방법

1. 정수n을 소수 중 가장 작은 수 2로 나누는 반복을 수행하는데 2로 나눠떨어지지 않을 때 다음 숫자로 +1을 해서 나눈다.

 

📌 코드

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

 

 

📌 결과

# 입력
72

#출력
2
2
2
3
3

# 입력
3

#출력
3

# 입력
6

#출력
2
3

# 입력
9991

#출력
97
103

 

 

🤔 시행착오.1

n = int(input())
if n == 1:
    print("")
while True:
    divisor = []
    for i in range(1,n+1):
        if n % i == 0:
            if i != 1:
                divisor.append(i)
    n = n // min(divisor)
    print(min(divisor))
    if n == 1:
        break

- 정상출력되지만 런타임에러가 발생한다. for문으로 n의 약수를 모두 구해서 가장 작은수를 리스트(divisor)에 담고, n을 가장 작은 수로 나눈 수의 약수를 또 다시 모두 구해서 가장 작은 수를 리스트(divisor)에 담아서  n이 나눠떨어지지 않을 때까지 반복을 수행하며 풀어서 불필요한 연산이 너무 많이 수행된다.

 

🤔 시행착오.2

n = int(input())
def soinsu(n):
    divisor = []
    for i in range(1,n+1):
        if n % i == 0:
            if i != 1:
                divisor.append(i)
    result = min(divisor)
    return result

while True:
    if n != 1:
        print(soinsu(n))
        n = n//soinsu(n)

-  정상출력은 되지만 시간초과 에러가 난다. 런타임에러를 해결하고자 함수를 사용한거지만 풀이가 시행착오1과 같기 때문에 너무 많은 연산이 수행된다.

 

 

📝 메모

- 시간초과랑 런타임에러 차이