原题链接

题解

关键因素：任何合数都可以分为最小质数乘上另外一个数

code

#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int> vis(n+5,0);

    for(int k=2;k<=n;k++)
    {
        if(!vis[k]) ans.push_back(k);
        for(int i=0;i<=ans.size()&&ans[i]*k<=n;i++)
        {
            vis[ans[i]*k]=1;//1不会重复赋值，所以时间复杂度是O(n)
            if(k%ans[i]==0) break;
        }
    }



    int q;
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        cout<<ans[x-1]<<"\n";
    }
    return 0;
}