Bakjoon Q11653 - C++

Q11653

---

Problem

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

Input

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

Output

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

예제 입력

72

예제 출력

2
2
2
3
3

나의 제출

#include <bits/stdc++.h>
using namespace std;

void division(int x);

int main(){
    int n;
    scanf("%d", &n);
    division(n);
    return 0;
 }

 void division(int x){
    if(x==1) // exit when input is 1 or end of recursion.
        exit(0);

    for(int i=2;i<=x;i++){
        if(x%i==0){//if divided by i
            x = x/i;
            printf("%d\n", i);
            division(x);
        }
    }
 }

추가 내용

recursion을 이용해서 구현하면 꽤 쉽게 풀리겠다고 생각을 했고, 실제로도 어렵지 않게 풀었던 것 같다. 먼저 소인수분해의 특성을 고려해서 약수를 떼어가고, 뗀 본체를 다시 원래 함수에다가 집어넣는 방식을 택했다.

1. escape은 반복해서 나눈 결과 1만 남으면 exit(0)이다. 처음에 return으로 시도했는데 자꾸 깔끔하게 종료가 안되고 좀 추잡(?)하게 몇 번 더 반복하다가 끝난다.

2. 2부터 나누기 시작하는데, if문을 통해서 나누어 떨어지는 경우에 나눈 수(인수)를 print하고 본체에서 그 수를 떼어내고 다시 함수에 넣는다(x = x/i). 안나눠진다면 i를 하나씩 올려가면서 나눠보는 것이고, 만약 자기 자신으로 나눌 때 까지 안나눠진다면(=소수) 자기 자신을 나눈 다음 1을 함수에 넣으므로 종료된다.

총평

처음 접했을 때는 살짝 골이 띵했는데 이정도면 할만 한듯 하다. 재귀함수를 이용하면 기분 좋을 정도로 깔끔하게 풀리는 문제.