Segmented Sieve

//  Created by Kaidul Islam on 18/4/16.
//  Copyright © 2016 Kaidul Islam. All rights reserved.
//
//
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(__typeof(n) i = 0; i < (n); i++)
#define rrep(i, n) for(__typeof(n) i = (n) - 1; i >= 0; --i)
#define rep1(i, n) for(__typeof(n) i = 1; i <= (n); i++)
#define FOR(i, a, b) for(__typeof(b) i = (a); i <= (b); i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define SZ(v) ((int)v.size())
#define INF (1 << 30)
#define PI acos(-1.0)
#define bitcnt __builtin_popcount
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof x)
#define eps 1e-9
#define pii pair<int, int>
#define couple make_pair
#define X first
#define Y second
#define vi vector<int>
#define vpii vector< pii >
#define si set<int>
#define SDi(x) sf("%d", &x)
#define SD2(x, y) sf("%d %d", &x, &y)
#define SD3(x, y, z) sf("%d %d %d", &x, &y, &z)
#define SDs(x) sf("%s", x)
#define pf printf
#define print(x) pf("%d ", x)
#define println(x) pf("%d\n", x)
#define output(x, y); pf("Case %d: %d", ++x, y)
#define newLine pf("\n")
#define sf scanf
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#if ( _WIN32 or __WIN32__ )
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define SDl(x) sf(LLD, &x)
#define MAX5 100005
#define MAX7 10000007
#define MAX9 1000000009
#define MOD9 1000000007
typedef long long i64;
typedef unsigned long long ui64;
const i64 INF64 = (i64) 1E18;

template<typename T> string toStr(T n) { ostringstream oss; oss << n; oss.flush(); return oss.str(); }
template<typename T> T toInt(string s) { T n = 0; istringstream sin(s); sin >> n; return n; }

class TimeTracker {
    clock_t start, end;
public:
    TimeTracker() {
        start = clock();
    }
    ~TimeTracker() {
        end = clock();
        fprintf(stderr, "%.3lf s\n", (double)(end - start) / CLOCKS_PER_SEC);
    }
};

struct Point {
    int x, y;
    Point(): x(0), y(0) {}
    Point(int a, int b): x(a), y(b) {}
    bool operator < (const Point& other) const {
        return x < other.x;
    }
};
// BitMask
int Set(int N, int pos) {
    return N |= (1 << pos);
}
int Reset(int N, int pos) {
    return N &= ~(1 << pos);
}
int Check(int N, int pos) {
    return (N & (1 << pos));
}
int toggle(int N, int pos) {
    return N ^= (1 << pos);
}

// direction array
//int dx[] = {0, -1, 0, 1};
//int dy[] = {-1, 0, 1, 0};
//int Dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
//int Dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
//int _row, _col;
//inline bool isValid(int i, int j) {
//    return i >= 0 and j >= 0 and i < _row and j < _col;
//}

#define MOD (MAX9 + 7)

inline void IncMod(int &x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

#define keyType int
class Compare {
public:
    bool operator() (keyType& lhs, keyType& rhs) const {
        return lhs > rhs;
    }
} compare;
// e.g. sort(all(arr), compare)


#define error(args...) { vector<string> _v; split(#args, ',', _v); err(_v.begin(), args); }

void split(const string& s, char c, vector<string>& result) {
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        result.push_back(x);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
    err(++it, args...);
}

/** Implementation **/

#define MAX 46350 // ~sqrt(INT_MAX)

vector<int> primes;
vector<bool> marked;

void sieve(int n) {
    int sqrtN = sqrt(n);
    marked = vector<bool>(n + 1, false);
    for(int i = 3; i <= sqrtN; i += 2) {
        if(!marked[i]) {
            for(int j = i; j <= n; j += (i << 1)) {
                marked[j] = true;
            }
            marked[i] = false;
        }
    }
    if(n >= 2) primes.push_back(2);
    for(int i = 3; i <= n; i += 2) {
        if(!marked[i]) {
            primes.push_back(i);
        }
    }
}

int arr[MAX5];

///Returns number of primes between segment [a,b]
void segmentedSieve2(unsigned int a, unsigned int b ) {
    if ( a == 1 ) a++;

    int sqrtn = sqrt ( b );

    memset ( arr, 0, sizeof arr ); ///Make all index of arr 0.

    for ( int i = 0; i < primes.size() && primes[i] <= sqrtn; i++ ) {
        int p = primes[i];
        int j = p * p;

        ///If j is smaller than a, then shift it inside of segment [a,b]
        if ( j < a ) j = ( ( a + p - 1 ) / p ) * p;

        for ( ; j <= b; j += p ) {
            arr[j-a] = 1; ///mark them as not prime
        }
    }

//    int res = 0;
    for ( int i = a; i <= b; i++ ) {
        ///If it is not marked, then it is a prime
        if ( arr[i-a] == 0 ) println(i);
    }
//    return res;
}

int segmentedSieve(unsigned int left, unsigned int right) {
    /*
    auto lbound = lower_bound(primes.begin(), primes.end(), left);
    for(auto it = lbound; it != primes.end() and *it <= right; ++it) {
        println(*it);
    }
    if(MAX > left and MAX < right) {
        left = MAX + 1;
    }
    */
    int sqrtR = sqrt(right);
    marked = vector<bool>(right - left + 1, false);

    for(int i = 1; i < primes.size() and primes[i] <= sqrtR; i++) {

        int offset = ((left + primes[i] - 1) / primes[i]) * primes[i];
        for(int j = offset; j <= right; j += (primes[i] << 1)) {
            marked[j - left] = true;
        }
        if(offset == primes[i]) {
            marked[offset - left] = false;
        }

    }

    int cnt = 0;
    if(left <= 2 and 2 <= right) {
        cnt++;
    }
    for(int i = max(((left & 1) ? left : left + 1), 3U); i <= right; i += 2) {
        cnt += !marked[i - left];
    }

    return cnt;
}

int main(int argc, const char * argv[]) {
#ifndef ONLINE_JUDGE
    assert(READ("input.txt"));
#endif
    int tcase;
    SDi(tcase);
    sieve(MAX);
    int m, n;
    int caseNo = 0;
    while(tcase--) {
        SD2(m, n);
        segmentedSieve2(m, n);
        if(tcase > 0) newLine;
    }
    return 0;
}