[백준] 11653번: 소인수분해 | C++ 풀이

# 문제

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

 

---

 

# 풀이

이래도 되나 싶을 정도로 간단한 풀이!

정답 소스코드를 바로 확인해보자.

 

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;

    for(int i=2; i*i <= n; i++){
        while(n%i == 0){
            cout << i << '\n';
            n /= i;
        }
    }
    if(n>1) cout << n;
    
    return 0;
}

우선 문제에서 요구한대로 n이 1인 경우에는 어떠한 반복문과 조건식에도 해당이 되지 않아 출력이 이루어지지 않는다.

 

n이 1이 아니라면 for문과 while문을 통해 소인수분해를 진행하면 된다. 이때 for문의 조건식은 의미없는 반복을 피하기 위해 i*i <= n으로 설정하였는데 구체적인 이유는 아래와 같다.

-- n이 소수일 경우 √n보다 큰 값으로 나누면 나머지가 0이 아니다. 따라서 반복을 계속할 이유가 없다. 예: 47의 제곱근, 약 6.85이므로 7로 나눠보면 나머지 5 / 61의 제곱근, 약 7.81이므로 8로 나눠보면 나머지 5

-- n이 소수가 아닐 경우 √n보다 큰 값으로 나누는 경우가 성립하지 않는다. 따라서 반복을 계속할 이유가 없다. 예: 6의 제곱근, 약 2.45이므로 3으로 나누는 경우는 성립하지 않음 (이전에 2로 나누어지고 반복문을 탈출, if문에 걸려 3을 출력) / 28의 제곱근, 약 5.38이므로 6으로 나누는 경우는 성립하지 않음 (이전에 2로 나누어지고 반복문을 탈출 if문에 걸려 7을 출력)

 

제일 작은 소수인 2부터 소인수분해를 진행하면 되는데, 만약 for문을 나온 후에도 n이 1보다 크다면 해당 수까지 소인수분해에 포함해야하므로 n을 출력하고 마무리한다. (예: 4, 6, 8 ...)

 

 

 

➕ 만약 for문의 조건식을 i <= n으로 둘 경우 if문을 넣지 않아도 원하는 대로 동작한다.  하지만 의미없는 반복의 증가로 시간이 더 많이 소요된다. (코드와 결과는 더보기에)

 

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            cout << i << '\n';
            n /= i;
        }
    }

    return 0;
}

 

 

 

 

 

 

 

 

---

 

 

 

11653번: 소인수분해