BOJ11653: 소인수분해 (Python)

문제

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

11653번: 소인수분해

 

코드

n = int(input())

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

 

풀이

n(소인수분해 할 정수 N) 에서 i 를 2부터 시작해서 나눈다. n에서 i를 나눈 나머지가 0일 경우 i가 n을 구성하는 소인수에 해당하므로 i를 출력하고 n은 i를 나눈 값으로 변경한다. 그리고 다시 i를 2부터 시작해서 나누는 것을 반복한다. 

 

✅ 처음에 이렇게 풀 생각을 못하고 n에서 소수들만 오름차순으로 나누어서 나머지가 0인 값들을 출력하면 되겠다고 생각했는데 정답보다 복잡한 생각이었고 백준에선 시간초과로 실패하였다. 정답처럼 굳이 소수만 뽑아서 나누지 않아도 2부터 시작해서 나눠질 값들은 다 나눠지는 것이므로 (ex. for문에서 i가 4에 도달할 경우 원래 n이 4로 나눠지는 것이 가능할지라도 앞선 for문에서 두 번의 2로 나눠졌을 것이기때문에 if n%i==0: 에 해당되지 않는 것이다.) 문제 없이 소인수들만 출력이 된다.