[11653] 소인수분해

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

11653번: 소인수분해

<문제>

N = 1천만이라 O(N)에도 통과는 된다.

 

낮은 수부터(상향식) 더이상 나누어 떨어지지 않을때까지(while) 나누어보는 방식이라면

정렬하지 않아도 자동적으로 정렬되어 저장되는 효과를 볼 수 있다.

아래는 O(N^1/2)에 구현한 방식이 되겠다.

<소스코드>

#include<stdio.h>
#include<vector>
using namespace std;
vector<int>v;
void factorization(int n) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            n /= i;
            v.push_back(i);
        }
    }
    if (n > 1)v.push_back(n);
}
int main(void) {
    int n = 0;
    scanf("%d", &n);
    factorization(n);
    for (auto& x : v) {
        printf("%d\n", x);
    }
    return 0;
}