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);
}