[백준 15965번] K번째 소수 (C++)

문제 링크 : https://www.acmicpc.net/problem/15965

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() {
    
    int K;
    cin >> K;

    vector<bool> isPrime(7500000, true);
    isPrime[0] = isPrime[1] = false;

    int cnt = 0;
    for (int i = 2; i < 7500000; i++) 
    {
        if (isPrime[i]) 
        {
            cnt++;
            if (cnt == K) 
            {
                cout << i << "\n";
                break;
            }
            for (long long j = (long long)i * i; j < 7500000; j += i) 
            {
                isPrime[j] = false;
            }
        }
    }

    return 0;
}

 

소수를 미리 구하면서 소수 개수를 카운팅하고, 이때 K번째 소수일 때 바로 멈추고 출력해준다.

K 값의 최대 범위를 보면 50만인데, 50만번째 소수는 7,368,787이다.

따라서 소수 구하는 범위는 7500000까지로 지정하여 입력 범위 내 모든 소수를 찾을 수 있도록 하였다.