백준 2960 - 에라토스테네스의 체(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2960

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

에라토스테네스의 체를 사용하는 문제입니다.

에라토스테네스의 체 기본 원리를 이용해 지워지는 K번째 수를 구하는 문제입니다.

여기서는 소수도 지워야함으로 이를 고려해주기만 하면 쉽게 풀 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

int N, K;
int check[1001];

void solve() {
    int remove = 0;
    check[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (check[i] == 1) continue;
        remove++;
        if (remove == K) {
            cout << i;
            return;
        }
        for (int j = i * 2; j <= N; j+=i) {
            if (check[j] == 0) remove++;
            if (remove == K) {
                cout << j;
                return;
            }
            check[j] = 1;
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    solve();
    return 0;

}

 

 

질문 및 조언은 댓글 남겨주세요