[C++][백준 31216] 슈퍼 소수

문제

접근 방법

친절하게 3000번째가 318137라는 것을 예제로 알려주었다.
해당하는 수만큼 에라토스테네스의 체로 소수를 걸러준 뒤 이후 반복문을 통해 슈퍼 소수에 해당하는 값인지 확인해 주면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
#define MAX_NUMBER 318137
vector<bool> isNotPrime;
vector<int> primes;
int T, n;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    isNotPrime = vector<bool>(MAX_NUMBER + 1);
    isNotPrime[1] = true;

    for (int i = 2; i * i <= MAX_NUMBER; ++i)
    {
        if (!isNotPrime[i])
        {
            for (int j = i * i; j <= MAX_NUMBER; j += i)
            {
                isNotPrime[j] = true;
            }
        }
    }

    for (int i = 2, j = 0; i <= MAX_NUMBER; ++i)
    {
        if (!isNotPrime[i]) // 현재 수가 소수이면
        {
            ++j;
            if (!isNotPrime[j]) // 현재 소수의 순번이 소수이면
            {
                primes.push_back(i);
            }
        }
    }

    cin >> T;
    while (T--)
    {
        cin >> n;
        cout << primes[--n] << "\n";
    }
}

풀이

소수인지 확인해 줄 수 있는 bool 배열을 만들어주고 현재 수가 소수인지, 소수라면 순번이 소수인지 확인해 주면 된다.