백준 알고리즘 11653번 : 소인수분해 python

백준 알고리즘 11653번 : 소인수분해 문제 바로가기

풀이 방법

정수 n을 입력했을 때 n을 소인수분해하여 결과를 한 줄씩 출력해야 한다.

1. n을 2부터 n-1까지의 숫자(i)로 나눈다. 이때 나머지가 0이 된다면 i를 출력한다.

2. n을 i로 나눈 값(몫)을 n에 저장한다.

3. 만약 나머지가 0이 아니라면 i의 값을 올린다. 이때 i의 값이 2라면 1을 올리고(3), i의 값이 2보다 초과한 값이라면 2씩 올린다.(2가 아닌 짝수는 소수가 아니기 때문에 확인할 필요가 없다.)

4. 위 과정을 반복한다.

5. n이 1이 된다면 프로그램을 종료한다.

​

소스코드

n = int(input())
i=2
while(True):
    if (n % i == 0):
        print(i)
        n=n//i
    else:
        if i>2: i+=2
        else: i+=1

    if n==1:
        break;