[Baekjoon] 소인수 분해

👀 문제 설명

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

72

 

예제 출력 1

2

2

2

3

3

 

예제 입력 2

3

 

예제 출력 2

3

 

예제 입력 3

6

 

예제 출력 3

2

3

 

예제 입력 4

9991

 

예제 출력 4

97

103

✍🏻풀이

에라토스테네스의 체를 사용해 N보다 작은 소수를 구하고, 이를 사용해서 소인수분해를 한다.

 

먼저 N 값을 입력받아, N + 1 크기의 int형 배열을 선언한다. 해당 배열을 1로 초기화한다.

2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.

2부터 시작해 남아있는 모든 수는 소수이다.

 

N보다 작은 소수이면서, N의 약수일 경우, 이 수는 소인수분해가 가능한 수이다. 벡터 v에 이 수를 담고, N을 k로 나눈다.

while문을 사용해 N != 1일 동안 위 문장을 반복하면 된다.

 

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 에라토스테네스의 체로 소수를 받아오고, 그걸 사용?
int a[10000001];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    fill_n(a, 10000001, 1); // a 배열을 모두 1로 초기화한다.
    for (int i = 2; i <= N; i++) {
        if (a[i] == 0) // 이미 지워진 수라면 건너뛴다.
            continue;
        
        // 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 구하기
        for (int j = 2 * i; j <= N; j += i) {
            a[j] = 0;
        }
    }
    
    vector<int> v;
    while (N != 1) {
        for (int k = N; k >= 2; k--) {
            if (a[k] == 1 && N % k == 0) { // N보다 작은 소수이면서, N의 약수이면 소인수분해할 수 있다.
                v.push_back(k);
                N /= k;
            }
        }
    }
    
    sort(v.begin(), v.end(), less<int>());
    
    for (int i = 0; i < v.size(); i++) {
        cout << v.at(i) << endl;
    }
    
    
    return 0;
}