백준 2960 에라토스테네스의 체 (구현)

가장 최근에 푼 구현문제이다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

여기서 중요한 것은 중복되는 수가 있다는 것이다. 예를 들어 2,4,6,8 순(2의 배수)으로 지운 뒤, 3,6,9(3의 배수) 순으로 지운다면 6이 중복되게 된다. 따라서 set을 이용해 중복을 제거시켜야 한다.

#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;

int n,k;
queue<int> que;
set<int> s;

void find() {		//큐에는 n까지의 소수를 미리 담아둠.
	for (int i = 2; i <= n; i++) {
		bool flag = true;
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				flag = false;
				break;
			}
		}
		if (flag == true)
			que.push(i);
	}
}

int main() {	
	cin >> n >> k;
	find();

	int cnt = 0;
	bool flag = true;
	while (flag) {
		int p = que.front();
		que.pop();

		for (int i = 1; i * p <= n; i++) {	//set을 이용하여 중복제거 ex)2와 3의 배수 6은 겹치기 때문.
			s.insert(i * p);
			if (s.size() == k) {	//set의 사이즈가 카운트 역할
				cout << i * p;
				flag = false;
				break;
			}
		}
	}
}