SPOJ prime1

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n)  for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))
#define vi vector<int>
#define vs vector<string>

int primenum;
vector<char> prime;
void eratos(llu n){
  primenum=0;
  prime.resize(n+1,1);
  for(llu i=2; i<=n; i++){
    if(i<=sqrt(n))
      if(prime[i]){
for(llu j=i*2;j<=n;j+=i)
 prime[j]=0;
      }
    if(prime[i])primenum++;
  }
}

void eratos2(int L,int U) {
  int d=U-L+1;
  bool flag[d];
  memset(flag,true,sizeof (flag));//all true
  for (int i=L%2;i<d;i+=2){ flag[i]=false;}//every position of even number false
  for (int i=3;i<d;i+=2)
    {
      if(!prime[i])continue;
      int mod=L%i;
      int t;
      if(mod>0)t=i-mod;
      else t=mod;
      if(L/i==1||L/i==0)t+=i;
      for(int j=t;j<d;j+=i){flag[j]=false;}
    }

  if (L<=1) flag[1-L]=false;
  if (L<=2 && U>1) {printf("2\n");}
  for (int i=L%2?0:1;i<d;i+=2) if (flag[i]==true) printf("%d\n",L+i);
}

void prepare( )
{
#ifdef WIN32
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

int main(){
  int nTests;
  scanf("%d ",&nTests);
  eratos(100000);
  repe(test,1,nTests) {
    llu inp, inp2;
    cin>>inp>>inp2;
    eratos2(inp, inp2);
    cout<<endl;
  }
  return 0;
}