[백준] 11653번 소인수분해

소인수분해

 

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

11653번: 소인수분해

 

풀이

자연수의 약수 중 소수인 수들을 소인수라 한다. ex) 10의 소인수는 2, 3, 5, 7

입력 받은 자연수를 소수로 나눠줘야 한다. 나눠지는 수가 소수인지 판단은 굳이 할 필요는 없다. (4는 2로 나눠지기 때문)

 

 

 

 

최초 제출 코드

N = int(input())

for i in range(1, N+1) :
    for j in range(2, i+1) :
        while True :
            if N == 1 :
                break
            elif N % j == 0 :
                N = N / j
                print(j)
                if N == 1 :
                    break
            else :
                break

 

해당 코드 제출 시 시간 초과가 났다.

나누려는 수가 소수인지 검증하는 for문은 굳이 필요가 없다.

 

 

 

정답

N = int(input())

i = 2
while True :
    if N == 1 :
        break 
    elif N % i == 0 :
        N = N / i
        print(i)
    else :
        i += 1