11653 - 소인수분해(백준)

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

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


// 소수를 미리 계산하는 에라토스테네스의 체 알고리즘
void calculate(int max, vector<int>& primes)
{
	// 소수인지 나타내는 bool 초기화
	vector<bool> is_prime(max + 1, true);
	// 0과 1은 당연히 소수가 아니므로 미리 false 처리
	is_prime[0] = is_prime[1] = false;

	// 2부터 특정 수까지 검사
	for (int i = 2; i <= max; i++)
	{
		// 소수이면
		if (is_prime[i])
		{
			// 소수 담는 데이터에 추가
			primes.emplace_back(i);
			// i의 배수들은 모두 소수가 아님. 제외시키기
			for (int j = i * 2; j <= max; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
}

int main()
{
	int N;
	cin >> N;

	vector<int> a;
	vector<int> primes;

	// 최대 소수 범위를 구하는데, 1을 더하면 놓치는 소수를 없애기 위함.
	// 소인수는 반드시 제곱근 이하의 소수만을 포함함.
	// 제곱근은  double 인데, int형으로 명시적 변환을 위해 int형으로 static_cast
	int max_prime = static_cast<int>(sqrt(N)) + 1;

	// 최대 소인수 범위에, 소인수 담은 primes 벡터.
	calculate(max_prime, primes);

	// primes 벡터 반복하면서
	for (int prime : primes)
	{
		// 해당하는 소수 값 찾기
		while (N > 1 && N % prime ==0)
		{
			a.emplace_back(prime);
			N /= prime;
		}
	}

	// 남은 소수들과 곱하면 원래 수가 되는 소수 포함하기 
	if (N > 1)
	{
		a.emplace_back(N);
	}

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

	return 0;
};

처음에, 에라토스테네스의 체 알고리즘을 안쓰고 해봤는데 통과되어서 놀랬다. 그래도 역시 시간이 오래 걸려서 
다시 쓰고 했더니 확실히 시간차가 줄었다.