题解 | Prime Number

#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int N=5e5+10;

bool st[N];
vector<int> prime;

void get_primes(int x)
{
    for(int i=2;i<=x;++i)
    {
        if(!st[i])  
        {
            prime.push_back(i);
            for(int j=i+i;j<=x;j+=i)
                st[j]=true;
        }
    }
}

int main()
{
    get_primes(N);

    int k;
    while(~scanf("%d",&k))
    {
        printf("%d\n",prime[k-1]);
    }
    
    return 0;
}

因为需要多组输入，所以用素数筛。试除法判断质数每次需要判断10000次，不清楚一共有多少组输入，故不采用试除法。

素数筛需要判断筛多少以内的质数，给定k最大为10000，假设没100个数里面只有10个质数（以100为例，远超10个），那么10000个质数需要到1e5，保险起见开5e5。