[백준] 2960번 에라토스테네스의 체 / C++

#문제

백준 2960번 에라토스테네스의 체

#풀이

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
vector<int> deleteNum;

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

	int n, k;
	cin >> n >> k;

	for (int i = 2; i <= n; ++i)
	{
		arr.push_back(i);
	}

	while (deleteNum.size() < k)
	{
		int p = arr[0];

		for (int i = 0; i < arr.size();)
		{
			if (arr[i] % p == 0)
			{
				deleteNum.push_back(arr[i]);
				arr.erase(arr.begin() + i);
			}
			else
			{
				++i;
			}
		}
	}

	cout << deleteNum[k - 1];

	return 0;
}

#정리

에라토스테네스의 체는 n보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘으로, 다음과 같은 규칙을 갖는다.

1. 2부터 n까지 모든 정수를 적는다.
   
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 p라고 하고, 이 수는 소수이다.
   
3. p 를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지운다.
   
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
   수를 지우고, 남은 수를 계속 비교할 수 있도록 만들어 주는 것. 모든 수를 비교했다면 p를 재설정하고 다시 비교하는 것이 핵심인 문제다. 나는 2개의 벡터 컨테이너를 만들어서 진행을 했다. 하나는 2부터 n까지의 수를 저장하는(앞으로 지워질) 컨테이너, 하나는 수를 출력하기 위해 1번 컨테이너에서 지우는 수를 저장하는 컨테이너. 모든 수를 받은 후, 지운 수를 받는 컨테이너의 원소 수가 k보다 많은 뒤 체크하여 실행되는 반복문을 돌렸다. 1번 컨테이너에서 가장 작은 수를 의미하는 p를 초기화하고, 컨테이너1의 모든 원소를 비교하되 원소를 지우면 다음 원소가 다시 앞으로 오니 조건을 유지했다.(i 변화 없음) 지우지 않았을 경우에만 i++하여 조건을 변경하였고, 반복문을 나와 컨테이너 2번에서 [k-1]원소를 출력하여 해결했다.