[백준] 11653번 소인수분해 / C++

#문제

#풀이

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> vec;

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

	int N;
	cin >> N;

	for (int i = 2; i <= N; ++i)
	{
		if (N % i == 0)
		{
			vec.push_back(i);
			N /= i;
			i = 1;

			if (N == 1)
			{
				break;
			}
		}
	}

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

	for (int i = 0; i < vec.size(); ++i)
	{
		cout << vec[i] << '\n';
	}

	return 0;
}

#정리

소인수분해(factorization), 하나의 자연수를 더 이상 나눌 수 없는 소수들의 곱으로 표현하는 것. 입력으로 주어진 N을 나누는 1이 아닌 가장 작은 수를 오름차순으로 출력하는 문제다. N이 1이 될 때까지, 나머지 연산이 0인 i를 vector에 삽입하고, 이 후에 std::sort() 함수를 사용하여 vector 내 원소를 오름차순으로 정렬하여 출력하여 풀었다.

#문제

#풀이

#정리

Enjoy Reading This Article?