欧拉筛+二分 题解

时间复杂度：$O(10^6+q \log n)$

Code:

#include<bits/stdc++.h>
using namespace std;
int n,q,pcnt;
int prm[1000005];
bool isp[1000005]={true,true};
int main(){
    for(int i=2;i<=1000000;i++){
        if(!isp[i]) prm[++pcnt]=i;
        for(int j=1;j<=pcnt;j++){
            if(i*prm[j]>1000000) break;
            isp[i*prm[j]]=true;
            if(i%prm[j]==0) break;
        }
    }
    cin>>q;
    while(q--){
        cin>>n;
        cout<<prm[lower_bound(prm+1,prm+1+pcnt,n)-prm-1]<<'\n';
    }
    return 0;
}