#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;
}