백준 11653번 소인수분해

<백준 11653번 소인수분해 - 마포 코딩박>

사용한 알고리즘: 에라토스테네스의 체


입력받은 N의 모든 소인수들을 출력해주는 문제였습니다.
문제풀이는 다음과 같습니다.

(1) N이 최대 10^7이므로 대략 4000까지 에라토스테네스 체로 소인수들을 구해줍니다. (N은 root(N) 이상의 소인수로 나눠지지 않습니다.)

(2) 재귀함수 돌려주면서 구해놓은 소인수중 N을 나누는 수가 있으면 이를 저장하고 다시 N/해당수 를 함수로 넣어주는 식으로 답을 구했습니다.

주의할점은 재귀함수를 돌리고 마지막에 남은 수가 1이 아닌경우 ( 구해놓은 소인수로 나눠지지 않은 경우 ) 이 또한 N의 소인수 이므로 저장해주어야 합니다.