[알고리즘] 백준 - 11653 소인수분해

문제

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

11653번: 소인수분해

 

설명

 소인수 분해는 하나의 수를 소수의 곱으로 나타낸 것입니다. 예를 들면, 예제처럼 72는 2*2*2*3*3 으로 나타낼 수 있습니다. 이와 같이 2가 여러 번 나올 수 있으므로 2로 나누어질때까지 나누고, 그 후에 다른 소수로 넘어가는 방법을 채택해야 하는 게 좋습니다.

 

코드

import sys

n = int(sys.stdin.readline())

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

 설명해보자면, 

1. n을 입력받습니다.

2. n이 1이 될 때 까지 while문을 돌립니다. (나누기가 다 끝나면 n이 1이 되기 때문) 

3. for문을 2부터 n까지 돌립니다. (range(2,n+1)인 이유는 n+1까지 범위를 지정해두어야 n일때도 실행이 되기 때문)

4-1. n이 i로 나눠지는지 비교 후, n이 i로 나눠지면 i를 출력합니다.

 4-2. n에는 n 나누기 i의 몫을 넣고 for문을 종료합니다. (break) 

 4-3. n이 1인지 체크 후 다시 2번으로 돌아가서 위의 과정을 반복합니다.

 

끝~