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

문제링크 : www.acmicpc.net/problem/11653  

문제요약

입력 : 소인수분해 할 수

 

출력 : N을 소인수분해한 결과를 한줄에 하나씩

 

소인수분해과정

 - 에라토스테네스의 체를 이용  →시간초과

 - i 를 2~N 까지 증가시키며 나누기 -> ㅇㅇ

이때 N 이 i 로 여러번 나누어지는 경우도 있으므로 if 문이 아닌 while 문을 쓴다.

ex) 100 → 2, 2, 5, 5

코드작성개요

필요한 변수 

N - 소인수분해를 할 수

 

출력

N을 나누었을때  나머지가 0이 되는 i 값

 

코드

N = int(input())
i = 2
while N != 1:
    if N == 0: break
    while N % i == 0:
        print(i)
        N /= i
    i += 1

cf) 채점이 굉장히 오래걸린다