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

문제접근🤔

• 2부터 n까지 수를 큐에 넣음
• 조건에 맞는 녀석만 큐에서 빼내고 k번째를 빼낼때까지 동작 반복

놓쳤던 부분😅

• while문을 queue의 size로 돌릴때는 큐의 사이즈가 변동이 있을 경우가 있기 때문에 조심해야함

코드😁

2020 KB

0 ms

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

int main(void)
{
	int n,k;
	int p;
	queue<int> q;
	int answer;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;

	for (int i = 2; i <= n; i++)
		q.push(i);
	while (k > 0)
	{
		p = q.front();
		answer = p;
		q.pop();
		k--;
		int i = 0;
		int q_size = q.size();
		while (k > 0 && q_size > i)
		{
			i++;
			if (q.front() % p == 0)
			{
				k--;
				answer = q.front();
				q.pop();
			}
			else
			{
				q.push(q.front());
				q.pop();
			}
		}
	}
	cout << answer;
	return (0);
}