n-th prime (Editorial)

n-th prime#11499

Written by @Yusif_M.

In this problem we need to find $n$ -th prime number. If you use brute force then we'll hit time limit. So here we'll use Eratosthenes Sieve algorithm. Also don't forget that in each test doing Erastosthenes Sieve algorithm will also hit time limit although this algorithm is quick. That's why we have to precompute all the primes. After that in every test case we will get $n$ and output the required $n$ -th prime number. Code will be like this:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <string>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_set>
#define ll long long 
#define ld long double
#define db double 
#define ch char
#define sg string 
#define st set
#define stck stack
#define pq priority_queue 
#define dq deque
#define vc vector 
#define bl bool
#define mp map
#define cp cout.precision 
#define ts to_string
#define mst multiset 
#define uost unordered_set 
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    vc<ll>primeNums;  //precomputed prime numbers will be stored in this vector
    vc<bl>isPrime(9000001,true);  //this boolean vector will determine if the number is prime or not if prime then it will store true in the index if the number is prime, otherwise it will stay false
    isPrime[0]=false,isPrime[1]=false;  //0 and 1 are not being considered as prime
    for(ll i=2;i<=9000000;i++)
    {
        if(isPrime[i])
        {
            primeNums.push_back(i);
            for(ll j=i*i;j<=9000000;j+=i)
            {
                isPrime[j]=false;
            }
        }
    }
    scanf("%lld",&t);  //get the number of test cases
    for(int c=0;c<t;c++)
    {
        scanf("%lld",&n);  //get index n
        printf("%lld\n",primeNums[n-1]);  //print the n-th prime number
    }
}

C++