第N个素数

Question

输入第一行包含正整数k。然后是k个正整数（每行一个）。数字不超过15000.输出对于每个数字n输出第n个按顺序素数。每个数字都应该在它的行中。

#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;
    }


}   

它给出了“时间限制”错误消息。我检查了几次，看看是否有任何错误，但我找不到。任何提示都将受到高度赞赏

Answer 1

对于每个数字n，您将生成一个完整的素数序列，最多为n。这是一个巨大的浪费时间。

仅供参考，第15000个素数是163841（从2开始是第1个）;我建议你制作一个163841元素的sieve of Eratosthenes，这将为你提供所有15000个素数，你需要同时回答这些问题;然后将它们收集成15000个元素的数组;然后才开始迭代输入数字并查找它们，这应该是超高速的（因为它只是普通的数组查找）。