[BOJ] 11653번 : 소인수분해

1. problem : 

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

 

 

2. solution 1 :

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

vector<int> prime_factor(int n) {
	vector<int> ans; 
	for (int i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ans.push_back(i); 
			n /= i;
		}
	}
	if (n != 1) ans.push_back(n);
	return ans; 
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	vector<int> ans = prime_factor(n);
	for (auto p : ans) cout << p << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/11653.cpp

basic-algo-lecture/0x12/solutions/11653.cpp at master · encrypted-def/basic-algo-lecture

아직 완벽히 이해가 가지않는다. ( N이 합성수라면, x <= root(N) 을 만족하는 소인수를 가진다.)