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

www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

크기 n + 1짜리 bool 타입의 벡터 v를 선언하여 다음과 같이 true로 초기화시켰다.

그 다음 지울 때마다 false로 바꿔주었다.

그리고 지울 때마다 index를 1 증가시켰다. index는 몇 번째 지운 것인지를 나타낸다.

지우지 않은 숫자들 중에 가장 작은 수는 num에 저장했다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<bool> v(n + 1, true);
	int index = 1;
	int answer = -1;
	while (true) {
		int num;
		for (int i = 2; i <= n; i++) {
			if (v[i]) {
				num = i;
				v[i] = false;
				if (index == k) {
					answer = i;
				}
				index++;
				break;
			}
		}
		if (answer != -1)
			break;
		int a = 2;
		while (a * num <= n) {
			if (v[a * num]) {
				v[a * num] = false;
				if (index == k) {
					answer = a * num;
					break;
				}
				index++;
			}
			a++;
		}
		if (answer != -1)
			break;
	}
	cout << answer;
	return 0;
}