[백준/BOJ] 백준 11653번 : 소인수분해

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

11653번: 소인수분해

에라토스테네스의 체를 응용하여 minfactor[](해당 인덱스의 가장 작은 소인수)를 구해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

int minfactor[10000001]; //해당 인덱스의 가장 작은 소인수를 구한다

//에라토스테네스의 체를 응용하여 minfactor를 만든다
void minfactorMake(int n)
{
	for (int i = 2; i <= n; i++)
		minfactor[i] = i;

	int sqrtn = sqrt(n);

	for (int i = 2; i <= sqrtn; i++)
	{
		//i가 소수일때
		if (minfactor[i] == i)
		{
			for (int j = i * i; j <= n; j = j + i)
			{
				//j의 가장 작은 소인수는 i가 된다
				minfactor[j] = i;
			}
		}
	}
}

void Solve(int n)
{
	minfactorMake(n);

	vector<int> result;

	while (n > 1)
	{
		result.push_back(minfactor[n]);
		n = n / minfactor[n]; //n의 가장 작은 소인수로 나눈다
	}

	sort(result.begin(), result.end());

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << "\n";
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;

	cin >> n;

	Solve(n);

	return 0;
}