[백준] 11653번: 소인수 분해 (C++)

11653번: 소인수 분해

---

문제 )

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

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

풀이)

소인수 분해를 하는 코드를 만들어 풀었다.

 

해당 코드에 대한 설명은 밑에 코드와 함께 주석으로 적어두었다.

 

 

#include <iostream>
using namespace std;
 
int main() {
 
    int n, x;
    cin >> n;
    // n은 변하면 안되므로 x를 따로 만들어 둔다.
    x = n;
 
    // 소수는 2부터이므로,
    for(int i = 2; i < n + 1; i++) {
        // 제곱수 이상부터는 소인수는 존재하지 않는다.
        if(i * i > n) break;
 
        // 2부터 소인수로 최대한 나눈다. 
        // 소인수로 나누어 나머지가 없다면 반복한다.
        while(x % i == 0) {
            cout << i << endl;
            x /= i;
        }
    }
 
    // 최대한 나눈 후, 1을 제외한 값을 표시해준다.
    if (x != 1) {
        cout << x << endl;
    }
 
    return 0;
}

 

---

출처 : https://www.acmicpc.net/problem/11653

11653번: 소인수분해