BOJ 2960 - 에라토스테네스의 체 링크
(2022.12.22 기준 S4)

문제

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
   위와 같은 순서대로 주어진 N, K로 알고리즘이 돌아갔을 때, K번째로 지워지는 수를 출력

알고리즘

문제 그대로 구현

풀이

에라토스테네스의 체를 모르면 이 문제가 안성맞춤일 것이다.
에라토스테네스의 체 알고리즘의 정확한 순서를 말해주기 때문. 다만, 차이점이 있다. N보다 작거나 같은 모든 소수를 찾을 때에는 N의 제곱근까지만 찾아보면 된다. 하지만, 이 문제는 소수도 지워나가야 한다. 그러므로 N까지 전부 차례대로 살펴봐야 한다.

문제 그대로 구현하면 되므로 더 이상 설명은 생략.

코드

• Python

N, K = map(int, input().split())

sieve = [False] * 2 + [True] * (N - 1) # 2부터 N까지 적는다.
k = 0 # 지운 횟수

for P in range(2, N + 1):
    if sieve[P]: # 지우지 않은 수 P를 찾자.

        # P를 지우고 K번째 지운 수인지 확인
        sieve[P] = False
        k += 1
        if k == K:
            print(P)
            exit()

        # 지워지지 않은 P의 배수를 크시 순서대로 찾아 지우고
        # K번째 지운 수인지 확인
        for Q in range(P * 2, N + 1, P):
            if sieve[Q]:
                sieve[Q] = False
                k += 1
                if k == K:
                    print(Q)
                    exit()

• C++

#include <iostream>
using namespace std;
int N, K;
bool sieve[1001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;

    for (int i = 2; i <= N; i++){ /* 2부터 N까지 적는다. */
        sieve[i] = true;
    }
    int k = 0; /* 지운 횟수 */

    for (int P = 2; P <= N; P++){
        if (sieve[P]){ /* 지우지 않은 수 P를 찾자. */

            /* P를 지우고 K번째 지운 수인지 확인 */
            sieve[P] = false;
            k += 1;
            if (k == K){
                cout << P;
                return 0;
            }

            /* 지워지지 않은 P의 배수를 크시 순서대로 찾아 지우고 */
            /* K번째 지운 수인지 확인 */
            for (int Q = P * 2; Q <= N; Q += P){
                if (sieve[Q]){
                    sieve[Q] = false;
                    k += 1;
                    if (k == K){
                        cout << Q;
                        return 0;
                    }
                }
            }
        }
    }
}