백준 11653 : 소인수분해 (파이썬)

https://www.acmicpc.net/problem/11653 문제풀이

11653번: 소인수분해

 

---

코드

n = int(input())
while n>1 :
    for i in range(2,int(n**.5)+1):
        if n%i == 0 :
            print(i)
            n //= i
            break
    else :
        print(n)
        break

풀이 

간단하게 2부터 나눠지는지 확인 후 나눠지면 출력해준 뒤 n을 해당 값으로 나눈 뒤 for문을 돌리면 된다.

중요한 건 이때도 제곱근까지만 확인하는 것!!

그리고 제곱근까지 안 나눠진다면 n값을 출력하면 끝(더이상 나눌수없기때문!!)