[Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3)

Baekjoon 문제풀이

서론

본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.

문제

Baekjoon 11653번 - 소인수분해:
https://www.acmicpc.net/problem/11653

11653번: 소인수분해

해법

이번 문제는 어떤 임의의 정수 N이 주어질때 이 N을 소인수분해하는 과정을 출력하는 문제이다. 소인수분해 작업은 대상이 작은 수라면 큰 문제가 되지 않겠지만 수가 커지면 커질 수록 필요한 작업량이 기하급수적으로 증가하게 된다. 특히 이번 문제는 주어진 N의 범위가 1 ≤ N ≤ 10,000,000로 제시되었기 때문에 우리는 좀 더 효율적으로 작업을 수행할 필요가 있다.

그래서 해법은 일단 기본적으로 소인수분해를 하는 방법은 동일하지만 중간중간에 나눠지는 수가 소수인지 판단하여 더이상 불필요한 검사작업을 하지 않도록 하는 것이다. N에 2부터 시작하는 i로 나누었을때 나머지가 0이면 해당 i값을 하나의 소인수로 출력하고, 아니라면 i를 1 증가시키면서 소인수분해를 수행하면 된다. 그런데 이 N이 소인수분해되는 과정에서 N이 소수일 경우에는 더이상 i를 나눠보면서 소인수가 더 있는지 검사할 필요가 없기때문에, N이 소수인지 판단하는 과정을 넣어 불필요한 작업을 최소화시킨다.

풀이

참고자료

위키피디아 - 소수판별법:
https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

소수판별법 - 위키백과, 우리 모두의 백과사전