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

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

11653번: 소인수분해

---

소인수분해

시간 제한	메모리 제한	제출	정담	맞힌 사람	정답 비율
1 초	256 MB	46822	25167	19681	52.615%

문제

정수 N이 주어졌을 때, 소인수 분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

코드

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값을 출력하면 끝(더이상 나눌수없기때문!!)