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

알고리즘을 실행했을 때 k번째 지우게 되는 수를 찾는 문제입니다.

소수를 찾는 에라토스테네스의 체를 사용합니다.
배열을 사용해서 처음 접근하는 부분을 체크하며 이 때 카운트를 해주면 됩니다.

 

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int main(int argc, char* argv[])
{
	int n, k;
	int arr[1010];

	memset(arr, 0, sizeof(arr));

	cin >> n >> k;

	for (int i = 2; i <= n; ++i) {
		for (int j = i; j <= n; j += i) {
			if (arr[j] == 0) {
				arr[j] = 1;
				--k;
			}
			if (k == 0) {
				cout << j << endl;
				return 0;
			}
		}
	}
	

	return 0;
}