//sieve筛选法求一段区间内的素数

#define maxn 1024000

int L,U;

int p[maxn],sz;//[0,sz)

bool flag[maxn];//U-L<=maxn

void sieve(int L,int U){

     int d=U-L+1;

     for(int i=0;i<d;i++)flag[i]=true;

     for(int i=(L%2!=0);i<d;i+=2)flag[i]=false;

     for(int i=3;i<=sqrt(U+0.0);i+=2){

        if(i>L&&flag[i-L]==false)continue;

        int j=L/i*i;

        if(j<L)j+=i;

        if(j==i)j+=i;

        j=j-L;

        for(;j<d;j+=i)flag[j]=false;

     }

     if(L<=1)flag[1-L]=false;

     if(L<=2)flag[2-L]=true;

     sz=0;

     for(int i=0;i<d;i++)if(flag[i]==true)p[sz++]=i+L;

}