[백준]11653_소인수분해

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

Solved

✔ 알고리즘 분류: 정수론, 소수 판정
✔ logic
1. 에라토스테네스로 소수 그룹을 만든다.
2. log2(10,000,000)=3,162.277 이므로 max값을 대충 3200쯤으로 해줬다.
3. 3200까지 for문을 돌며 i번째 값이 소수이고, 주어진 수 N의 약수일 때 몫의 개수만큼 i를 출력한다.

using namespace std;
#include <iostream>

bool e[3200];

void era() {
	e[1] = true;
	for (int i = 2; i < 3200; i++) {
		if (e[i] == true) continue; //소수가 아니면
		for (int j = i * 2; j < 3200; j += i) {
			if (e[j] == true) continue;
			e[j] = true;
		}
	}
}

int main() {
	int n;
	cin >> n;
	era();
	if (n == 1) {
		return 0;
	}
	for (int i = 2; i < 3200; i++) {
		if (n == 1) break;
		if (e[i] == true) continue;
		while (n % i == 0) {
			cout << i << '\n';
			n /= i;
		}
	}
	if (n > 1) cout << n << "\n";
	return 0;
}