11653번 : 소인수분해

[ 문제 ]

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

[ Input ]

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

[ Output ]

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

---

[ 풀이 ]

소인수분해 문제는 코딩공부할 때 무조건 풀어보는 문제인 것 같다. 오랜만에 보니 엇? 했지만 엇! 할 것도 없었다 ㅋㅋ

 

소인수는 1보다 큰 자연수로 이루어져야 하므로 소인수는 2부터 점점 커지도록 한다.

소인수를 1만큼씩 키우면서 input의 인수가 될 수 있는지 확인할 것이다.

-> input을 소인수로 나눴을 때 나머지가 0이면 인수이다.

인수를 판별했다면 해당 인수로 input을 나누어서 값을 update 해준다.

또한 update하고 인수에 1을 더하면 안된다. 4와 8 같은 같은 소인수를 여럿 가질 수 있으므로 나눠지지 않을 때 1을 더한다.

이 과정을 반복하다가 input이 1이 되면 소인수분해를 끝낼 것이다. 

[ 코딩 ]

# 정수 input
num = int(input())
# 소인수의 시작
i = 2

# num이 1이 된다면 소인수분해는 끝!
while num != 1:
    # 인수로 나눴을 때 0이 된다면 소인수
    if num % i == 0:
        print(i)
        num = num // i
    # 안되면 넘어가자
    else:
        i += 1