[BAE/<JOON> 문제풀이] 2960. 에라스토네스의 체

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

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

에라스토네스의 체 문제이다.

 

지워진 수인지 아닌지만 판단해서 지워지지 않은 수일 경우를 세면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	int m;
	cin >> n;
	cin >> m;
	vector<int> arr;
	arr.resize(n + 1);
	arr.assign(n + 1, 0);
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (arr[i] == 1) continue;
		arr[i] = 1;
		if (++cnt == m) {
			cout << i << endl;
			return 0;
		}
		for (int j = i * 2; j <= n; j += i) {
			if (arr[j] == 0) {
				if (++cnt == m) {
					cout << j << endl;
					return 0;
				}
			}		
			arr[j] = 1;
		}
	}

	return 0;
}