10852 - Less Prime

Author: Ismail Hosen

Daffodil International University

Problem Link

//Please follow from main function

#include<bits/stdc++.h>



using namespace std;



/// Typedef

typedef long long           ll;

typedef unsigned long       ul;

typedef unsigned long long  ull;

typedef vector<int>         vi;

typedef vector<vi>          vvi;

typedef vector<ll>          vll;

typedef pair<int,int>       pii;

typedef pair<ll,ll>         pll;

typedef vector< pii >       vii;



#define loop(i, y)          for(int i=0; i<int(y); i++)

#define sci(x)              scanf("%d", &x)

/// Constants

#define MAX                 100000005

#define MOD                 1000000009

#define base                1000000007

#define eps                 1e-9

#define INF                 1llu<<61    // 2,305,843,009,213,693,952

#define inf                 1<<29       // 536,870,912

#define PI                  acos(-1.0)  // 3.1415926535897932



int status[MAX];vector<int>prime;void seive(){    status[0]=status[1]=1;    for(int i=4; i<MAX; i+=2) status[i]=1;    for(int i=3; i*i<=MAX; i+=2){        if(status[i]==0){            for(int j=3*i; j<MAX; j+=(2*i)){                status[j]=1;            }        }    }    for(int i=2; i<MAX; i++) if(!status[i]) prime.push_back(i);}



int main()

{

    seive();

    int n, x, tc;

    //loop(i, 1000) cout<<prime[i]<<endl;

    sci(tc);

    while(tc--){

        cin>>n;

        x=n/2;

        loop(i, x){

            if(prime[i]>x){

                x=i;

                break;

            }

        }

        cout<<prime[x]<<endl;

    }

    return 0;

}