segmented_seive

// first call seive() ,
//this fun returns no. of prime between [a,b] interval

int segment_seive(ll a,ll b)
{
    if(b<2)return 0;
    if(a<2)a=2;
    bool mark[b-a+1];
    memset(mark,true,sizeof(mark));


    for(int i=0;i<prime.size() && (ll)prime[i]*prime[i]<=b;i++){
        ll j=(a/prime[i])*prime[i];
        if(j<a)
            j+=prime[i];
        if(j<(ll)prime[i]*2)j=prime[i]*2;
        for(;j<=b;j+=prime[i]){
            mark[j-a]=false;
        }
    }
    int ret=0;
    for(int i=a;i<=b;i++){
        ret+=mark[i-a];
    }

    return ret;
}