N-th prime number

Question

Input First line contains a positive integer k. Then k positive integers follow (one in each line). The numbers don't exceed 15000. Output For each number n output the n-th by order prime number. Each number should be in its line.

#include <iostream>
#include <vector>
#include <math.h>

long long getNthPrime(int n)
{
    long long size{};

    if(n<11)
    {
        size=n*n;
    }
    else{
        size=n*log(n)*log(n);
    }

    std::vector<int>is_prime(size+1, 1);
    is_prime[0]=is_prime[1]=0;
    is_prime[2]=1;
    int count=1;
    if(n==1)
    {
        return 2;
    }
    for(long long i=3; i<=size; i+=2)
    {
        if(is_prime[i]==1)
        {
            count++;
            if(count==n)
            {
                return i;
            }
            for(long long j=i*i; j<=size; j+=i)
            {
                is_prime[j]=0;
            }
        }

    }

}

int main() {

    int n, k;
    std::cin>>k;
    std::vector<int>arr;

    for(int i=0; i<k; i++)
    {
        std::cin>>n;
        arr.push_back(n);
    }

    for(int i=0; i<k; i++)
    {
        std::cout<<getNthPrime(arr[i])<<std::endl;
    }


}   

It gives "time limit" error message. I checked several times to see if there is anything wrong withing but I couldn't find. Any hints would be highly appreciated

Answer 1

For each number n, you are generating a whole sequence of primes up to n. This is a colossal waste of time.

FYI, the 15000th prime is 163841 (starting with 2 being 1st); I suggest you make a sieve of Eratosthenes of 163841 elements, this will give you all 15000 primes you need to answer the queries, all at once; then collect them into an array of 15000 elements; only then start iterating through the input numbers and looking them up, which should be superfast (as it's just plain array lookup).