Segmented Sieve

#include<bits/stdc++.h>
using namespace std;

#define       ll       long long int
#define       ull      unsigned long long int
#define       ld       long double

#define       pf       printf
#define       sf       scanf

#define       pb       push_back
#define       pob      pop_back
#define       ph       push
#define       pp       pop
#define       mp       make_pair
#define       ins      insert
#define       f        first
#define       sc       second

#define       eps      (double)(1e-7)
#define       M        (ll)(1e6)
#define       LM       (ll)(1e18)
#define       mod      (ll)(1e6+7)
#define       MAX      32000

vector <int> primes;
bool marked[M];

void sieve(){
  primes.pb(2);
  for(int i=3;i<=MAX;i+=2){
    if(!marked[i]){
      primes.pb(i);
      for(int j=i*i;j<=MAX;j+=i){
        marked[j] = true;
      }
    }
  }
}

void segSieve(int u,int l){
  bool isPrime[(l-u)+1];
  int cnt = 0;
  for(int i=0;i<(l-u)+1;i++){
    isPrime[i] = true;
  }
  for(int i=0;primes[i]*primes[i]<=l;i++){
    int curPrime = primes[i];
    ll fmul = (u/curPrime)*curPrime;
    if(fmul<u){
      fmul += curPrime;
    }
    for(int j=fmul;j<=l;j+=curPrime){
      isPrime[j-u] = false;
    }
    if(fmul==curPrime){
      isPrime[fmul-u] = true;
    }
  }
  for(int i=0;i<(l-u)+1;i++){
    if(isPrime[i]){
      cout << i+u << endl;
    }
  }
}

int main()
{
  sieve();
  segSieve(2,17);

  return 0;
}