[백준 2960] 에라토스테네스의 체

문제 풀이

기존의 에라토스테네스의 체에서 약간 변형의 문제입니다.

보통은 소수를 제외하고 그 소수의 배수를 모두 지우는 형태가 에라토스테네스의 체 구현이지만, 이 문제에서 요구하는 건 소수를 찾았을 때도 제거하고 그의 배수들도 모두 제거하면서 지나갑니다.

 

N = 7, K = 3이면

제거하는 순서를 나열하면 다음과 같습니다.

2 4 6 (2의 배수) 3 (3의 배수) 5 (5의 배수) 7 (7의 배수)

따라서 3번째 제거된 수는 6입니다.

 

중복되는 수를 제거 방지를 위해서 prime변수를 선언해서 제거했더라면 false로 시키고 카운팅 합니다.

카운팅 횟수가 K번째와 같게 된다면 그때가 바로 K번째로 제거된 수입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
bool prime[1001];

void eratosthenes()
{
	fill(prime, prime + 1001, true);
	prime[0] = false;
	prime[1] = false;

	int cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		// i의 수를 아직 안지웠다면?
		if (prime[i] == true)
		{
			cnt++;
			prime[i] = false;
			if (cnt == k)
			{
				cout << i << endl;
				return;
			}
		}
		// i의 배수를 모두 확인
		for (int j = i + i; j <= n; j += i)
		{
			// j 수를 아직 안지웠다면?
			if (prime[j] == true)
			{
				cnt++;
				prime[j] = false;
				if (cnt == k)
				{
					cout << j << endl;
					return;
				}
			}
		}
	}
}

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

	cin >> n >> k;
	eratosthenes();
	return 0;
}